Поиск дубликатов в массиве

Задача

Есть массив целых от 1 до N. Нужно определить, есть ли в этом массиве повторяющиеся значения.

Решение

Задачу можно решить несколькими способами. Первое, что приходит в голову - отсортировать исходный массив и сравнивать соседние элементы. Затраты по времени и по расходуемой памяти будут зависеть от алгоритма сортировки, например, при быстрой сортировке временная сложность будет O(nlogn +n-1) и емкостная сложность (память) будет O(logn).

<br />bool has_duplicates(int *array, int len)<br />{<br /> quicksort(array, 0, len-1);<br /><br /> for(int i=1;i < len;i++)<br /> if(array[i-1]==array[i]) return true;<br /><br /> return false;<br />};
Другое решение - пошагово обходить массив и в каждой итерации проверять значение элемента, сравнивая с информацией о предыдущих итерациях, сохраняемой в дополнительном контейнере. Таким контейнером может быть массив размера N и полностью заполненный нулями. Индекс элемента в массиве - значение от 1 до N (точнее от 0 до N-1), значение элемента - количество "индекса" в исходном массиве. Это проще выглядит на примере:

// исходный массив, со значениями от 1 до 9
src_array = [1,3,8,4,2,9,3,9]

// дополнительный массив на 9 элементов (что бы уместились от 1 до 9)
add_array = [0,0,0,0,0,0,0,0,0]

// после обработки исходного массива результирующий будет выглядеть так:
// одна единица, одна двойка, две тройки, одна четверка, одна восьмерка и две девятки
add_array = [1,1,2,1,0,0,0,1,2]

<br />bool has_duplicates(int *src_array, int len, int minN, int maxN)<br />{<br /> // допускаем, что входящие данные валидны<br /> int add_len = maxN-minN+1;<br /> int *add_array = new int [add_len];<br /><br /> // что-то не помню, можно ли по другому забить массив нулями :(<br /> for(int i=0;i < add_len;i++) add_array[i] = 0;<br /><br /> for(int i=0;i < len;i++)<br /> if(++add_array[src_array[i]-1]>1)<br /> // здесь можно добавить return true;<br /> // но для наглядности просто выведем результат<br /> std::cout<< src_array[i]<< add_array[src_array[i]-1]<< std::endl;<br /><br /> delete [] add_array;<br /><br /> return false;<br />}
Сложность такого алгоритма будет O(n), затраты памяти будут зависеть от диапазона данных - O(maxN-minN). Кроме этого, требуется, что бы было известно максимальное значение элементов из исходного массива, в противном случае либо будет затрачиваться дополнительное время на его поиск, либо понадобиться значительно больше памяти (например, что бы поместить все целые числа).

Вывод

Из двух предложенных решений первое требует дополнительно реализации сортировки, но является более универсальным и имеет преимущества при больших размерах исходного массива и большом диапазоне значений. Второй метод проще реализуем (если предположить, что в первом случае нет готовой функции сортировки), но требует дополнительной информации о диапазоне значений и при большом диапазоне - большие затраты памяти.