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

[avva]

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

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

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

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

Comments

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

[avva.livejournal.com]

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

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

[blueher.livejournal.com]

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

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

[avva.livejournal.com]

Ну вы почитайте его внимательней и разберитесь, как он работает.

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

[blueher.livejournal.com]

Ваша правда - был неправ. Сыплю голову пеплом.

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

[avva.livejournal.com]

Бывает :)

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

[blueher.livejournal.com]

Навскидку придумалось - берем блум фильтр

http://en.wikipedia.org/wiki/Bloom_filter

и отбираем в ассоциативный массив только те числа которые "потенциально уже есть". Потом проходим второй раз и проверям уже только их. Оценочную функцию прикинуть не берусь ;)

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

[avva.livejournal.com]

Да, тут действительно оценить трудно ;)

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

[blueher.livejournal.com]

Если массив можно менять, то где-то так:

for(var i=0;;i++) {
int p = N[i];
if (p == N[p-1]) {
print(p); break;
} else {
swap(N[i],N[p-1])
}
}

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.