?

Log in

No account? Create an account
задачка (программистское) - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

задачка (программистское) [янв. 5, 2011|04:08 pm]
Anatoly Vorobey
Задачка для программистов и интересующихся. Наверняка известная, но мне в такой форме не встречалась, и понравилась.

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

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

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

Comments:
Страница 1 из 2
<<[1] [2] >>
[User Picture]From: relf
2011-01-05 02:44 pm
если время O(N), а массив только читается, то это лучше или как?
(Ответить) (Thread)
[User Picture]From: avva
2011-01-05 02:54 pm
лучше, да.
(Ответить) (Parent) (Thread)
(Удалённый комментарий)
[User Picture]From: avva
2011-01-05 02:55 pm
Ну оказались вы где-то внутри цикла, и что?
(Ответить) (Parent) (Thread)
(Удалённый комментарий)
(Удалённый комментарий)
(Удалённый комментарий)
(Удалённый комментарий)
(Удалённый комментарий)
(Удалённый комментарий)
(Удалённый комментарий)
From: (Anonymous)
2011-01-05 03:16 pm

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

veryverylong P = 0;

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

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

(понятно, что P всё равно должна быть размером O(N)).
(Ответить) (Thread)
[User Picture]From: avva
2011-01-05 03:18 pm

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

да, увы :)
(Ответить) (Parent) (Thread)
[User Picture]From: mgar
2011-01-05 03:25 pm
O(N) времени и О(sqrt(N)) места вижу, а вот лучше...
(Ответить) (Thread)
[User Picture]From: avva
2011-01-05 03:49 pm
Интересно, а что это за O(sqrt(N)) места, расскажите?
(Ответить) (Parent) (Thread) (Развернуть)
From: (Anonymous)
2011-01-05 03:31 pm
можно считать, что в каждую ячейку массива записан указатель на другую ячейку массива. таким образом, у нас есть связный список. или даже несколько связных списков, с разными началами, но со сливающимися хвостами.

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

итого О(1) памяти, O(N) времени. быстрее нельзя.
(Ответить) (Thread)
[User Picture]From: avva
2011-01-05 03:40 pm
Неплохая идея, но как вы найдете именно начало цикла? Алгоритм, который вы упоминаете, всего лишь поместит вас куда-нибудь внутрь его.
(Ответить) (Parent) (Thread) (Развернуть)
From: (Anonymous)
2011-01-05 03:52 pm
int f(int A[N]){
int index, int tmp,

index = 0;
tmp = A[index];
while( index != tmp ){
index = tmp;
tmp = A[index];
}
return tmp;
}
(Ответить) (Thread)
[User Picture]From: avva
2011-01-05 03:54 pm
Так можно легко в бесконечном цикле побежать.
(Ответить) (Parent) (Thread) (Развернуть)
From: blueher
2011-01-05 04:19 pm

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

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

При этом гарантированно находим число которое встречается чаще всего, что ещё круче чем исходное условие.
Ну и ещё и алгоритм - проще некуда
Человек который его придумал - гений.
(Ответить) (Thread)
[User Picture]From: avva
2011-01-05 04:28 pm

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

Это гениальный алгоритм, но он решает совсем другую проблему, а не эту. Для него необходимо, чтобы какой-то элемент встречался более половины раз.
(Ответить) (Parent) (Thread) (Развернуть)
From: mudak
2011-01-05 04:40 pm
берем интервалы значений 1:k и k+1:N-1, в одном из интервалов число попавших значений будет больше длины интервала, следовательно там есть повторения, делим интервал пополам, повторяем. вроде бы O(N*log(N)) на месте O(1)
(Ответить) (Thread)
[User Picture]From: penguinny
2011-01-05 04:42 pm
Тривиальный алгоритм, всё же, должен быть не с O(N) памяти, а с O(log N).
Задачку видел раньше, но не думал; что-то пока не могу придумать, как сделать O(1) памяти (как хорошо, что вы прячете решения :).
(Ответить) (Thread)
[User Picture]From: penguinny
2011-01-05 04:43 pm
Извините, уже вижу что сморозил глупость. Комментарий выше прошу считать бессмысленным.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: whichferdinand
2011-01-05 05:01 pm
O(n) времени, О(sqrt(n)) места:

Создать счетчики для элеметов в [0, sqrt(n)), [sqrt(n), 2*sqrt(n)), ..., [(sqrt(n)-1))*sqrt(n)...n),
Пройти по массиву обновляя счетчики, и найти тот интервал, в котором больще, чем sqrt(n) элеметов. Дальше просто переписать эти эелемнты , отсортировать, и найти нужный.


O(n log n) времени:
Та же идея, но с интервалами [0, n/2), [n/2, n). В одном из них будет больше чем n/2 элементов, а в другом меньше. Потом просто рекусивно искать.
(Ответить) (Thread)
[User Picture]From: whichferdinand
2011-01-05 05:06 pm
"Дальше просто переписать эти эелемнты , отсортировать, и найти нужный."

Ой, не получится, все равно их слишком много.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: vieni
2011-01-05 05:10 pm
Можно начать их сортировать, передвигая каждый элемент на то место, на котором он по порядку должен находиться. Есть число=5, то на 5е месте, а то число, которое было на пятом месте - опять же на его место. Остановимся, если какой-то элемент уже окажется на своем месте.
(Ответить) (Thread)
[User Picture]From: avva
2011-01-05 05:12 pm
Это требует O(N) места, так что не лучше, чем просто посчитать в отдельном массиве, сколько раз каждый встречается.
(Ответить) (Parent) (Thread)
[User Picture]From: dmage_ru
2011-01-05 05:43 pm
http://www.everfall.com/paste/id.php?5lhydzgs5tt4
вроде получилось O(n) времени и O(1) места :)
(Ответить) (Thread)
[User Picture]From: avva
2011-01-05 05:46 pm
Браво! Простой и понятный код, люблю Питон :) Все верно!
(Ответить) (Parent) (Thread)
[User Picture]From: oulenspiegel
2011-01-05 06:20 pm
int xorAll = 0;
int xorArray = 0;

for (int i = 0; i < N; i++) { xorAll ^= i; } // это можно и умнее посчитать, без цикла
for (int value : array) { xorArray ^= value; }

int answer = xorAll ^ xorArray;


(Ответить) (Thread)
[User Picture]From: avva
2011-01-05 06:22 pm
"Поксорить все" решает некую задачу. Но это не эта задача :)

Вы упустили то, что не все числа от 1 до N-1 должны быть в массиве, повторов может быть много разных.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: pilpilon
2011-01-05 06:23 pm
а ну так в области значений нуля нету.
рассмотрим записанные в массиве числа, как адреса в том же массиве, тогда из нуля у нас растет однонаправленный список, который зацикливается, и начало его не входит в цикл.

пошлем бегать по списку традиционно два указателся , один с единичной скоростью, другой с двойной. за о(н) один нагонит другой. далее еще за о(н) мы найдем длину цикла, пусть она равна м. пустим из нуля два указателя с единичной скоростью, но со сдвигом в м. в какой-то момент (еще о(н)) они будут показывать на одно число из разных мест.
(Ответить) (Thread)
[User Picture]From: avva
2011-01-05 06:31 pm
Да, все верно!
(Ответить) (Parent) (Thread)
[User Picture]From: oulenspiegel
2011-01-05 06:44 pm
блин, дурь написал)

int found = 0;

for (int i = 0; i < N; i++)
{
int value = Math.abs(arr[i]);
if (arr[value] < 0) { found = value; break; }
arr[value] = -arr[value];
}
(Ответить) (Thread)
[User Picture]From: avva
2011-01-05 06:54 pm
Это изменяет массив и пользуется O(N) места - с таким же успехом можно этот подсчет делать в отдельном массиве.
(Ответить) (Parent) (Thread) (Развернуть)
Страница 1 из 2
<<[1] [2] >>