задачка (программистское)

[avva]

Задачка для программистов и интересующихся. Наверняка известная, но мне в такой форме не встречалась, и понравилась.

Дан массив размером N, в нем есть только числа от 1 до N-1 (необязательно все, необязательно по порядку). Очевидно, какие-то из них повторяются. Найти какое-то число, которое встречается в массиве больше одного раза.

Суть в том, чтобы сделать это с как можно лучшей сложностью времени и места. Скажем, тривиально сделать это за O(N) времени с O(N) места. Можно лучше. Исходный массив не бесплатный: его можно менять, но это считается в бюджет места.

Update: все скрытые комментарии с правильными решениями раскрываются. Не заглядывайте в комментарии, если хотите дальше думать сами - там есть много правильных решений. Оптимальное решение этой проблемы выполняет задачу за O(N) времени, O(1) места.

Comments

Re: За один проход, с одной переменной

[avva.livejournal.com]

Если массив можно менять, то есть много способов за O(N), да :)

Re: За один проход, с одной переменной

[blueher.livejournal.com]

Ещё вариант - заводим массив M размерностью k, заполняем нулями. Для каждого элемента инкрементируем M[N[i]/k]. В конце прохода смотрим на M - если в одном из элементов M число больше чем N/k - наши повторения из этого диапазона. Повторяем пока искомый диапазон не станет меньше k.

Re: За один проход, с одной переменной

[blueher.livejournal.com]

Да, необязательно проходить весь массив - можем останавливаться как только один из элементов M стал больше N/K (ну это так, уже оптимизации)

Re: За один проход, с одной переменной

[avva.livejournal.com]

Да, это кто-то предлагал уже ниже - кажется, дает O(sqrt(N)) места и что-то вроде O(N*log(N)) времени.

Re: За один проход, с одной переменной

[blueher.livejournal.com]

K здесь не зависит от N, поэтому по месту здесь O(1). С другой строны - по времени действительно O(N*log(N)), причём константы (которые выкидываются оценочной функцией) зависят от K.