Вы ищете предмет с числом повторений, отличным от нуля (мод 3).Я думаю, что я бы сделал это рекурсивно:
- разделить массив пополам
- найти элементы с числом повторений, отличным от нуля (мод 3), в каждой половине
- объединить половинки, сохраняя счет для неравных ключей, и добавляя счет для равных ключей
- вычеркнуть любое с количеством = 0 (мод 3)
- вернуть это как набор значений длятекущая часть ввода.
Даже не пытаясь оптимизировать вещи, выходящие за рамки базового алгоритма (например, , а не , не заботясь о сохранении только двух битов на счетчик), это выглядит довольно неплохоЧто ж.Я включил код, чтобы сгенерировать достаточно большой контрольный пример (например, 1500+ элементов) и распечатать размеры создаваемых карт.Кажется, что в любой момент времени на картах, которые он создает, находится максимум около 50 элементов (т.е. он использует только две карты одновременно, и самое большое, что я видел, составляет около 25 элементов).Технически, в его нынешнем виде, я считаю, что это в настоящее время что-то вроде O (N log N), но если вы переключились на контейнер на основе хеша, я думаю, вы ожидаете O (N).
#include <map>
#include <iterator>
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <time.h>
class zero_mod {
unsigned base;
public:
zero_mod(unsigned b) : base(b) {}
bool operator()(std::pair<int, int> const &v) {
return v.second % base == 0;
}
};
// merge two maps together -- all keys from both maps, and the sums
// of equal values.
// Then remove any items with a value congruent to 0 (mod 3)
//
std::map<int, int>
merge(std::map<int, int> const &left, std::map<int, int> const &right) {
std::map<int, int>::const_iterator p, pos;
std::map<int, int> temp, ret;
std::copy(left.begin(), left.end(), std::inserter(temp, temp.end()));
for (p=right.begin(); p!=right.end(); ++p)
temp[p->first] += p->second;
std::remove_copy_if(temp.begin(), temp.end(),
std::inserter(ret, ret.end()),
zero_mod(3));
return ret;
}
// Recursively find items with counts != 0 (mod 3):
std::map<int, int>
do_count(std::vector<int> const &input, size_t left, size_t right) {
std::map<int, int> left_counts, right_counts, temp, ret;
if (right - left <= 2) {
for (size_t i=left; i!=right; ++i)
++ret[input[i]];
return ret;
}
size_t middle = left + (right-left)/2;
left_counts = do_count(input, left, middle);
right_counts = do_count(input, middle, right);
ret = merge(left_counts, right_counts);
// show the size of the map to get an idea of how much storage we're using.
std::cerr << "Size: " << ret.size() << "\t";
return ret;
}
std::map<int, int> count(std::vector<int> const &input) {
return do_count(input, 0, input.size());
}
namespace std {
ostream &operator<<(ostream &os, pair<int, int> const &p) {
return os << p.first;
}
}
int main() {
srand(time(NULL));
std::vector<int> test;
// generate a bunch of data by inserting packets of 3 items
for (int i=0; i<100; i++) {
int packets = std::rand() % 10;
int value = rand() % 50;
for (int i=0; i<packets * 3; i++)
test.push_back(value);
}
// then remove one item, so that value will not occur a multiple of 3 times
size_t pos = rand() % test.size();
std::cerr << "Removing: " << test[pos] << " at position: " << pos << "\n";
test.erase(test.begin()+pos);
std::cerr << "Overall size: " << test.size() << "\n";
std::random_shuffle(test.begin(), test.end());
// Note that we use a map of results, so this will work if multiple values
// occur the wrong number of times.
std::map<int, int> results = count(test);
// show the results. Should match the value shown as removed above:
std::copy(results.begin(), results.end(),
std::ostream_iterator<std::pair<int, int> >(std::cout, "\n"));
return 0;
}