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

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

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

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

eNose,

Вообще-то, есть System Idle, благодаря которому мы имеем шанс сразу получить обнулённые страницы.

Можно попробовать опереться на другие сортировки. Скажем, поразрядная потребует выделения 64-кратного объёма исходного массива без обнуления и поиск дубликата потребует довести сортировку в среднем до половины, но на таком мелком массиве это не окупается.
Шелл позволит теоретически найти дубликат на больших списках (а Хоар, соответственно, обнаружить равенство разделяющему элементу), но вероятность этого меньше 1/2.

Исходный массив обладает тем свойством, что его элементы не нули и XOR любой пары элементов кроме искомых не ноль. Интересно, можно ли за это зацепиться?

GrasQtRМожет связный список?
А нафига?

Panshin,

Кто-то сказал, что число 36 253 в этой последовательности есть?

Требуется указать число, либо его индекс в некотором массиве. Возможных индексов - n, чисел - 1000000.
Если отсортировать массив (O(n*ln(n))), то проверка каждого индекса на правильность - O(1).

Каким свойством вместо монотонности может обладать массив, чтобы наличие дубликатов элемента по заданному индексу проверялось за O(1)?

Nitica,

Бедный процессор.
И вообще, если массив "по умолчанию" заполнен нулями, то, позвольте спросить, кто его заполнил?

DENIS_CHELИсходный массив с числами произвольной длины... Но не больше 1 000 000.
1 000 001 ;)

JoFanПока приходит на ум какая нибудь быстрая сортировка, где в операции сравнения и будем проверять на равенство
Быстрые сортировки потому и быстрые, что сравнивают друг с другом не все n(n-1)/2 пар.

NiticaAbstraction,
Бедный процессор.

то есть сортировка, по Вашему мнению, менее затратна, чем просто один пробег по массиву. Указатели - самое менее затратное средство в вычислениях как ни крути :)

И вообще, если массив "по умолчанию" заполнен нулями, то, позвольте спросить, кто его заполнил?

это псевдо-код :) в Visual C, например, точно будут нулики
Массив в 500 элементов, а мы отжираем 2 Mb. Спорный выигрыш.

Visual C++ 6.0, насколько помню, выделяемую такой конструкцией память не обнуляет. Для примера. В любом случае, если мы не надеемся на то, что у системы завалялись обнулённые страницы, это придётся делать нашему процессу, увы.


А если танцевать от хэш-таблицы? Функция h(x)=x%n, получаем n классов (некоторые из которых, возможно, пустые), оба дубликата в одном классе; время создания - O(n), среднее время проверки одного класса - O(1). Правда, при этом совершенно не используем ограниченность спектра значений.

eNoseпри иницилизации массива ничего физически не выделяется.
Я что-то пропустил?
После инициализации мы имеем адрес начала области памяти, к которой можно обращаться. Откуда она берётся, в таком случае?

NiticaAbstraction,

Массив в 500 элементов, а мы отжираем 2 Mb. Спорный выигрыш.

в формулировке задачи вроде как ясно сказано, что ограничений по памяти нет.
Ограничений нет. Но эти 500 1250 страниц кому-то надо выделить, а потом эти полмиллиона миллион с хвостиком машинных слов кому-то обнулить.

eNose,

Проверил на C#, проверил на C++.
Я прав ;)

eNose,

Где ж я вам его возьму?
Но вообще, идея выделять память только при обращении к ней подразумевает, что мы обращаемся не напрямую к памяти, а вызываем некоторый метод, который вначале проверяет, выделили ли нам эту память. Что выливается в потерю производительности.

ZyK_BotaNЯростный Мечпропущено...
ты перепутал с "обратной" задачей, когда повторяются все числа кроме одного

а че бы подобное решение не придумать.А что бы нам не придумать алгоритм факторизации за линейное время.

Сделать XOR последнего элемента всему остальному массиву можно без проблем. Потом предпоследнего и так далее, пока не получится ноль в середине - несколько десятков ассемблерных команд на всю процедуру, среднее время O(n ² ).
Сделать XOR соседей (превращая (a ₁ ,a ₂ ,a ₃ ,...) в (a ₁ ^a ₂ ,a ₂ ^a ₃ ,a ₃ ^a ₄ ,...)), по пути анализируя, не получилось ли нуля, можно без проблем. Повторить придётся столько раз, каково расстояние между дубликатами; среднее время O(n ² ), но если нам известно, что дубликаты близко, может оказаться полезно.
Вариант с хэш-таблицей вроде бы работает за O(n). В одном списке можно искать предыдущим способом.