Если говорить об алгоритме без sql, то я бы предложил следующее:

0) Отсортировать исходный массив.
1) Совершить по отсортированному массиву 1 проход, сравнивая соседние числа между собой...

MasterZivСколько в итоге
экземпляров этого числа в массиве -- два или четыре ? или даже может быть три ?

Товарищь, который формулировал задание, был хитрый.


И мое решение и Еноза это корректно отработает... Вопрос в том будет ли это верным ответом на вопрос...

PS Не люблю задачи типа "Докажите что..."

eNoseDENIS_CHELЕсли говорить об алгоритме без sql, то я бы предложил следующее:

0) Отсортировать исходный массив.
1) Совершить по отсортированному массиву 1 проход, сравнивая соседние числа между собой... ограничения только по использованию процессора, а не по памяти.
так что проще:
1) создать второй массив [1..1000000] и в него закидывать элементы первого по индексам.
если перед присваиванием не ноль, значит это и есть искомое неуникальное число.

Я над этим думал - сортировка подсчетом, но вся прелесть, что нам не надо сортировать до конца:)

Но есть один момент создать массив в 1 000 000 обнулить его то же затратно, в исходной задаче сказано "массив произвольного размера", сортировка 3-х чисел будет быстрее:)

AbstractionЧисла, укладывающиеся в 20 бит. Ограничение на время процессора, но не на память. Хм.
Заводим служебный массив в 2 Mb, инициализируем нулями. Для каждого числа в массиве, если соответствующая ячейка служебного массива ноль, пишем один; если была единица - ура, мы нашли клиента.
Ничего быстрее мне в голову не приходит.

Это и есть сортировка подсчетом, выше уже предлагали...

GrasQtRromapost,

Может связный список?

Городить этот огород еще хуже сортировки...