Быстрый алгоритм для поиска двух одинаковых

[kirill94]

Даны числа $\{a_1, a_2, \ldots\ , a_n\}$.
Необходимо ответить, есть ли среди них два одинаковых числа за время $O(n\times\log(n))$.

Задача прямо из первой темы учебника, а я сразу задумался.

[Deggial]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
Причина переноса: формулы не оформлены ТеХом

Оформите формулы ТеХом. Инструкции по оформлению формул здесь или здесь (или в этом видеоролике).
После исправлений сообщите в теме Сообщение в карантине исправлено, и тогда тема будет возвращена.

[Deggial]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»
вернул
формулы поправил - наведите мышкой и посмотрите, как оформлять формулы.
Для возврата темы следует писать сюда

[Narn]

Указание: если бы было дополнительно известно, что список отсортирован, то за какое время решалась бы задача?
Кстати, это вопрос не для математического, а скорее для программистского форума.

[Tanechka]

kirill94, а что вообще можно сделать за $O(n\log(n))$?

[Shadow]

Бинарное дерево наверное имеют ввиду.

[Евгений Машеров]

Зачем так сложно, с деревом?
Если последовательность чисел упорядочена, место их в последовательности зависит от их значения. Где могут быть расположены два одинаковых числа?

[Tanechka]

Евгений Машеров, если последовательность упорядочена, то её можно просто пробежать за $O(n)$... а вот упорядочить её как раз можно за $O(n\log(n))$ любым известным способом.

[Евгений Машеров]

(Оффтоп)

Спасибо, товарищ капитан!

[Gh0stik]

Верно вопрос скорее всего по программированию...

Если величины $a_i$ ограничены, например так: $a_i \in [A..B]$, то поиск можно выполнить за $O(n)+B-A+1$.

При чтении данных заполняем массив $[A..B]$, если прочитали $a_k$ то увеличиваем на 1 элемент $a_k$. После достаточно "пробежать" весь массив $[A..B]$ и проверить есть ли в нем хотя бы одно число более 2, следовательно в исходном множестве присутствуют как минимум два одинаковых элемента.

[Cash]

Что-то я не понял. $a_n = \sin n$. Что мы пробегаем и что увеличиваем?

[ИСН]

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

[Cash]

XOR?

[ИСН]

Естественно.