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

[avva]

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

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

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

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

Comments

[(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;
}

[(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 и в нем посчитать, сколько раз встречается каждый элемент.

[(Anonymous)]

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

int f(int A[N]){
int index, stop_index, loop_index;
int i, tmp, loop_size;

i = 0;
index = A[0];
while( ( index != A[index] )&&( i < N ) ){
index = A[index];
i ++;
}
// К этому моменту мы гарантированно находимся в цикле
// либо попали на элемент массива, хранящий свой номер,
// что означает повторение
if( index == A[index] ){
return index;
}

// Определим размер цикла
loop_size = 1;
stop_index = index;
while( A[index] != stop_index ){
index = A[index];
loop_size ++;
}

// Теперь параллельно идем по 2 маршрутам:
// - движемся по циклу (корректно выбрав начальную позицию)
// - идем маршрутом от нулевого элемента
// Как только индексы совпали, мы нашли повторяющийся элемент.
loop_index = stop_index;
i = loop_size - N % loop_size;
while( i > 0 ){
loop_index = A[loop_index];
i --;
}

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

return index;
}

Возможно, я где-то наврал в индексах, но идея решения, надеюсь, ясна.

[avva.livejournal.com]

Ага, это уже похоже на правильное решение. Та часть, которую вы называете "корректно выбрав начальную позицию", у вас не то чтобы очень понятна в коде, но если приглядеться как следует, то да, она сделает то, что нужно. Очень подробно не проверял, и может есть какие-то off-by-1 итд., но в целом это один из вариантов правильного решения, да. Поздравляю! :)

Я заскриню ваш комментарий на некоторое время, с вашего позволения.