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

[avva]

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

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

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

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

Comments

[relf.livejournal.com]

если время O(N), а массив только читается, то это лучше или как?

[avva.livejournal.com]

лучше, да.

[alter.livejournal.com]

Конечно же, лучше. Опишите алгоритм, пожалуйста. Лично мне кажется, что алгоритма O(N) без места (или даже с O(1) места) быть не может.

[avva.livejournal.com]

Ну оказались вы где-то внутри цикла, и что?

[avva.livejournal.com]

Вот это другое дело, это действительно полное решение :) Вы знали или сейчас решили?

Я его заскриню пока.

[relf.livejournal.com]

ну совсем без места не получится - переменные тоже место жрут, но O(1) кажется реальным
а идея похожа на предложенную ниже ilyaraz, только нужно проработать детали

[migmit.livejournal.com]

Да, похоже, прокатит. Отличная идея.

Тривиальное не-решение:

[(Anonymous)]

veryverylong P = 0;

for(i = 0; i < N; i++)
{
Q = 1 << arr[i];

if( N & P )
{
// Нашли дупликат
return i;
}
else
{
N &= P;
}
}

(понятно, что P всё равно должна быть размером O(N)).

Re: Тривиальное не-решение:

[avva.livejournal.com]

да, увы :)

[avva.livejournal.com]

Есть, кстати, существенно другое, чем у ilyaraz, но хуже по времени, решение за O(NlogN) времени и O(1) места. Я сначала до него додумался, а потом уже до того же, что и ilyaraz.

Но, конечно, O(N) времени и O(1) места - лучшее, что может быть.

[mgar.livejournal.com]

O(N) времени и О(sqrt(N)) места вижу, а вот лучше...

[(Anonymous)]

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

понятное дело, в любом из этих списков есть цикл, причем длины меньше N. то есть есть элемент, на который указывают два указателя — последний в цикле и тот, что перед первым. эти два и будут повторяющимися элементами. а находить циклы в связных списках мы, слава заратустре, умеем (еще одна задача с интервью, пускаем два указателя с разными скоростями). чтобы не начать случайно изнутри цикла, начнем с последнего элемента, на него точно ничего не указывает.

итого О(1) памяти, O(N) времени. быстрее нельзя.

[avva.livejournal.com]

Неплохая идея, но как вы найдете именно начало цикла? Алгоритм, который вы упоминаете, всего лишь поместит вас куда-нибудь внутрь его.

[avva.livejournal.com]

Старая задачка, "засвеченная" очень. У нас ее давно не спрашивают. Хотя я ее знаю немного в другом варианте для K=2 (оговаривается не кол-во проходов, а O(N) времени, ну и места O(1), понятно).

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

[avva.livejournal.com]

Интересно, а что это за O(sqrt(N)) места, расскажите?

[(Anonymous)]

int f(int A[N]){
int index, int tmp,

index = 0;
tmp = A[index];
while( index != tmp ){
index = tmp;
tmp = A[index];
}
return tmp;
}

[avva.livejournal.com]

Так можно легко в бесконечном цикле побежать.

[(Anonymous)]

Я сначала придумал идею: в каждом элементе исходного массива запоминать, встречался ли элемент с данным номером, затем реализовал ее в виде 2-х вложенных циклов (с общей сложностью O(N)), а затем в виде одного, но забыл изменить пройденный элемент.
Вторая версия.

int f(int A[N]){
int index, int tmp,

index = 0;
tmp = A[index];
while( index != tmp ){
A[index] = index; // добавленная строка
index = tmp;
tmp = A[index];
}
return tmp;
}

[avva.livejournal.com]

Не уверен насчет произвольного K.

[(Anonymous)]

Опять неверно. Пришлось остановиться, чтобы подумать.
Третий вариант.

int f(int A[N]){
int index, next_index;

index = A[0];
while( index != A[index] ){
next_index = A[index];
A[index] = index;
index = next_index;
}
return A[index];
}

[avva.livejournal.com]

Это лучше, но т.к. это меняет в общем случае O(N) элементов массива, это не лучше, чем просто ввести дополнительный массив размером N и в нем посчитать, сколько раз встречается каждый элемент.

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

[blueher.livejournal.com]

http://www.cs.utexas.edu/users/moore/best-ideas/mjrty/index.html

При этом гарантированно находим число которое встречается чаще всего, что ещё круче чем исходное условие.
Ну и ещё и алгоритм - проще некуда
Человек который его придумал - гений.

[(Anonymous)]

ну не все так печально. в конце алгоритма число шагов, пройденное до совпадения, кратно длине цикла. поэтому если сейчас еще раз запустить указатель с начала списка и другой указатель с текущего положения, они пересекутся на входе в цикл.

[lazyreader.livejournal.com]

Просто quicksort - разве это не есть именно O(NlogN)? Просто предикат сравнения выбирается с тем побочным действием, что программа останавливается, если операнды равны.

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

[avva.livejournal.com]

Это гениальный алгоритм, но он решает совсем другую проблему, а не эту. Для него необходимо, чтобы какой-то элемент встречался более половины раз.