?

Log in

задачка (программистское) - Поклонник деепричастий [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) (Развернуть)
[User Picture]From: bespechnoepero
2011-01-05 07:16 pm
Первое число отнимается от второго. Если получается ноль, то задача решена, а если нет, то результат запоминается как число К. Далее, первое число минусуется от всех остальных, какждый раз результат сравнивается с ноль и с К. Если совпал, то задача решена, если нет, то переходим к следующему циклу, в котором все начинается от второго числа. И так далее, пока не найдем или ноль или К.

Примитивно, конечно, но я ж не программист. Макро еще могу состряпать, а если требуется скрипт, то я выбрасываю такой софт, как непригодный к практическому использованию в реальных условиях.
(Ответить) (Thread)
[User Picture]From: meshko
2011-01-05 07:20 pm
Тут время O(n^2), а трюк с вычитанием ничего не дает на самом деле, все равно что сравнить каждое число с каждым.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: alaev
2011-01-05 07:19 pm
Вопрос о правилах подсчёта: если N очень велико, то для хранения одного числа нужно O(log(N)) места, то есть весь массив займет O(N*log(N)) места. То же самое касается, например, сравнения двух чисел: если они очень большие, то понять, равны ли они, можно только за O(log(N)) шагов. Учитывается ли это в Ваших оценках?

Или же мы считаем, что числа невелики, заведомо влезают в какой-нибудь регистр, и все операции занимают один шаг?
(Ответить) (Thread)
[User Picture]From: avva
2011-01-05 07:22 pm
Обычно в таких задачах придерживаются среднего пути: с одной стороны, считаем, что все числа достаточно невелики, влезают в регистр, и обычные операции между ними занимают один шаг; с другой стороны, если в ходе алгоритма нужно повторить отдельно и по-разному какой-то шаг для каждого разряда числа (например, какая-то побитовая обработка), то это считается множителем logN, а не константным.

Тут есть определенное противоречие, но на практике это неплохо работает.
(Ответить) (Parent) (Thread)
[User Picture]From: bespechnoepero
2011-01-05 07:57 pm

Есть еще один смешной способ

Не уверен, что будет работать, но можно порассуждать.
Допустим, что повторяющихся чисел в массиве нет. Следовательно, если к каждому числу массива поочередно добавить все числа, присутствующие в массиве, то мы получим новый массив, в котором на каждом месте будет сумма E всех чисел от 1 до N-1, исключая те, которые не присутствуют в массиве. Можно и умножать вместо сложения, тогда у нас будет факториал F на каждом месте (возможно, не полный).

Если же в в массиве есть повторяющиеся числа, то, по крайней мере, два числа в конечном массиве будут отличаться от суммы Е (или факториала F). Далее уже просто.
(Ответить) (Thread)
[User Picture]From: bespechnoepero
2011-01-05 09:08 pm

То есть, наоборот...

Если же в в массиве есть повторяющиеся числа, то, по крайней мере, два числа в конечном массиве будут равны сумме Е (или факториалу F), а все остальные отличаться, поскольку одно и то же число будет использовано более одного раза, как необходимо для вычисления суммы или факториала.
(Ответить) (Parent) (Thread)
[User Picture]From: cryinstone
2011-01-05 08:25 pm
Используем сумму арифметической прогрессии
Time: O(N)
Space: O(1)
(Ответить) (Thread)
[User Picture]From: avva
2011-01-05 08:34 pm
Нет, вы неправильно поняли условие.
(Ответить) (Parent) (Thread)
From: (Anonymous)
2011-01-05 09:36 pm
Для начала возьмем A = X[N] (будем для простоты считать, что нумерация элементов идет с 1)

Затем начнем повторять A = X[A]

Рано или поздно мы зациклимся. Но не сразу - поскольку ни один элемент не может содержать N и указывать на ячейку X[N], наша исходная точка не может принадлежать циклу. "Началом" цикла будет некая ячейка X[M], на которую есть сразу две ссылки - одна на начальной части пути (не принадлежащей циклу), вторая - уже в самом этом цикле. То есть M лежит в двух разных ячейках - это и есть искомое значение. (Сам цикл, в принципе, может быть вырожденным и состоять из единственной ячейки, ссылающейся сама на себя).

Выполним операцию "A = X[A]" N раз - это дает нам гарантию того, что A уже принадлежит циклу. Запомним это A как A0.

Начав с A0, будем выполнять "A = X[A]" (считая шаги), пока A снова не станет равным A0, - так мы определим длину цикла L (если цикл выроженный, то можно на этом и закончить).

Еще раз вернемся в начало (к последнему элементу). Сделаем L шагов указателем A, и в этот момент начнем идти (тоже от последней ячейки) еще одним указателем B. Будем двигать их синхронно - таким обазом, когда последний из них (B) войдет в цикл, первый (A) как раз закончит первый обход этого цикла. Так мы найдем начало цикла, элемент X[M].

return M;
(Ответить) (Thread)
[User Picture]From: avva
2011-01-05 09:43 pm
return M;

Да, все правильно. Поздравляю! :)
(Ответить) (Parent) (Thread)
[User Picture]From: mad_ghost
2011-01-05 10:41 pm
Я наверняка очень плохой программист :( Но я не знаю проще чем:
class Program
{
static void Main(string[] args)
{
int[] arr = { 1, 2, 3, 4, 5, 4, 3, 2, 3, 4, 5, 6, 4, 5, 7 };
Console.Write(GetRepeatDigit(arr));
Console.ReadLine();
}

static int GetRepeatDigit(int[] arr)
{
Hashtable t = new Hashtable();
foreach (int d in arr)
{
if (t[d] != null) return d;
t[d] = 1;
}
return 0;
}
}
один проход массива
hashtable заполняется до первого найденного повторяющегося числа.
(Ответить) (Thread)
From: kapla55
2011-01-05 11:57 pm
Рассмотрим граф вершинами которого являются числа от 1 до N. Если в нашем массиве А[k] = j, то будем считать что в графе имется дуга из узла k в узел j. Очевидно, что часть узлов будет иметь больше одной входящей дуги и все узлы будут иметь как минимум одну исходящую дугу. Две входящие дуги в один узел будут соответствовать одинаковым числам в исходном массиве и такой узел обязан быть частью нетривиального цикла на графе. Найти цикла на графе можно с помощью двух бегущих указателей один в два раза быстрее другого. После этого пройдясь еще раз по цепочке найдем узел с двумя входными дугами.

Итого не более 4 раз проходим по массиву и используем О(1) дополнительной памяти (два указателя).
(Ответить) (Thread)
[User Picture]From: meshko
2011-01-06 12:40 am
tak a kak najti uzel s 2 vhodnymi dugami?
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: Sascha [blogspot.com]
2011-01-06 02:51 am
Отличная перефразировка задачи о поиске начала цикла в односвязном списке, долго думал. :)
(структура списка: i -> a[i], начинаем из N, чтобы не попасть в цикл сразу, идём двумя итераторами, ну Вы эту задачу наверняка знаете)

Расскажите, плз, скрытым комментарием, как делать за O(N log N) и O(1) памяти? Ничего естественного в голову не приходит :)
(Ответить) (Thread)
[User Picture]From: avva
2011-01-06 08:34 am
Вот кто-то уже написал за меня, как делать за O(Nlog(N)) времени и O(1) места:

http://garconnumeroun.livejournal.com/128464.html

Edited at 2011-01-06 08:35 (UTC)
(Ответить) (Parent) (Thread)
(Удалённый комментарий)
[User Picture]From: avva
2011-01-06 10:06 am
за O(N) :)
(Ответить) (Parent) (Thread)
(Удалённый комментарий)
[User Picture]From: vieni
2011-01-07 02:52 pm
Мне кажется, как-то так и надо, только не менять элементы массива, а найти цикл и из этого цикла уже найти то число, которое повторяется. Под переменные там пойдет больше, чем 1, конечно... Но какая-то маленькая константа.
(Ответить) (Parent) (Thread)
Страница 1 из 2
<<[1] [2] >>