Да, вы можете сделать намного лучше.

1. Сортируйте их (O (n) для простых целых чисел, O (n * log n) в целом), то дубликаты гарантированно будут смежными, что ускоряет их поиск O (n)

2. Используйте хеш-таблицу, также O (n). Для каждого элемента (а) проверьте, есть ли он уже в хэш-таблице; если да, то это дубликат; если нет, поместите его в хеш-таблицу.

edit

Метод, который вы используете, похоже, выполняет O (N ^ 2) сравнений:

for i = 0; i < length; ++i           // will do length times
    for j = i+1; j < length; ++j     // will do length-i times
        compare

Итак, для длины 5 вы делаете 4 + 3 + 2 + 1 = 10 сравнений; для 6 вы делаете 15 и т.д. (N ^ 2) / 2 - N / 2, если быть точным. N * log (N) меньше при любом достаточно высоком значении N.

Насколько велик N в вашем случае?

Что касается уменьшения количества хеш-коллизий, лучший способ - получить лучшую хеш-функцию :-D. Предполагая, что это невозможно, если вы можете создать вариант (например, другой модульный), вы сможете выполнить вложенный хэш.

1. Сортировка массива O (n log n) в худшем случае - сортировка слиянием / heapsort / сортировка двоичного дерева и т. Д.

2. Сравните соседей и вытащите совпадения O (n)

Сохранять структуру на основе хеш-таблицы от значения до подсчета; Если ваша реализация C ++ не предлагает std :: hash_map (пока что не является частью стандарта C ++! -), используйте Boost или загрузите версию из Интернета. Один проход по коллекции (то есть O (N)) позволяет вам выполнить отображение значение-> счетчик; еще один проход по хеш-таблице (очевидно, <= O (N)), чтобы идентифицировать значения со счетчиком> 1 и выдавать их соответствующим образом. В целом O (N), что не соответствует вашему предложению.

А сортировку пробовали? Например, используя такой алгоритм, как быстрая сортировка? Если производительность для вас достаточно высока, это будет простой подход.

Если известно, что это список целых чисел, и если известно, что все они находятся между A и B (например, A = 0, B = 9), создайте массив BA элементы и создают контейнеры BA.

В очень конкретном случае (список простых целых чисел) я предлагаю вам просто подсчитать их, поскольку вы все равно не можете различать разные целые числа:

for(int i = 0; i < countOfNumbers; i++)
    counter[number[i]]++;

Если они равны ] различимые, создайте массив списков и добавьте их в соответствующий список.

Если они не являются числами, используйте std :: map или std :: hash_map, сопоставив ключи со списками значений.

Самым простым, вероятно, является просто отсортировать список, а затем перебирать его в поисках дубликатов.

Если вам что-то известно о данных, возможны более эффективные алгоритмы.

Например, если вы знали, что список большой и содержит только целые числа от 1 до n, где n довольно мало, вы можете использовать пару логических массивов (или растровое изображение) и сделать что-то вроде этого:

bool[] once = new bool[MAXIMUM_VALUE];
bool[] many = new bool[MAXIMUM_VALUE];
for (int i = 0; i < list.Length; i++)
    if (once[ value[i] ])
        many[ value[i] ] = true;
    else
        once[ value[i] ] = true;

Теперь , many [] содержит массив, значения которого наблюдались более одного раза.

Большинство людей, упоминающих решения хеширования / неупорядоченной карты, предполагают, что время вставки и запроса составляет O (1), однако в худшем случае это может быть O (N). Кроме того, вы аннулируете стоимость хеширования объекта.

Лично я бы вставлял объекты в двоичное дерево (вставка O (logn) для каждого) и держал счетчик на каждом узле. Это дало бы время построения O (nlogn) и обход O (n) для идентификации всех дубликатов.

Если я правильно понял вопрос, то это самое простое решение, которое я могу придумать:

std::vector<T> input;
typedef std::vector<T>::iterator iter;

std::vector<std::pair<iter, iter> > output;

sort(input.begin(), input.end()); // O(n lg n) comparisons

for (iter cur = input.begin(); cur != input.end();){
  std::pair<iter, iter> range = equal_range(cur, input.end(), *cur); // find all elements equal to the current one O(lg n) comparisons
  cur = range.second;
  output.push_back(range);
}

Общее время работы: O (n log n) . end () также используется гораздо чаще, чем необходимо, и его можно легко кэшировать.

В зависимости от предполагаемого размера групп, equal_range может быть не самым эффективным выбором. Я предполагаю, что он выполняет двоичный поиск, чтобы получить логарифмическую сложность, но если каждая группа состоит только из пары элементов, простое линейное сканирование было бы быстрее. В любом случае первоначальная сортировка преобладает над затратами.