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

[avva]

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

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

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

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

Comments

[relf.livejournal.com]

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

[avva.livejournal.com]

лучше, да.

[avva.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]

да, увы :)

[mgar.livejournal.com]

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

[avva.livejournal.com]

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

[(Anonymous)]

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

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

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

[avva.livejournal.com]

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

[(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]

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

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

[blueher.livejournal.com]

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

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

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

[avva.livejournal.com]

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

[mudak.livejournal.com]

берем интервалы значений 1:k и k+1:N-1, в одном из интервалов число попавших значений будет больше длины интервала, следовательно там есть повторения, делим интервал пополам, повторяем. вроде бы O(N*log(N)) на месте O(1)

[penguinny.livejournal.com]

Тривиальный алгоритм, всё же, должен быть не с O(N) памяти, а с O(log N).
Задачку видел раньше, но не думал; что-то пока не могу придумать, как сделать O(1) памяти (как хорошо, что вы прячете решения :).

[penguinny.livejournal.com]

Извините, уже вижу что сморозил глупость. Комментарий выше прошу считать бессмысленным.

[whichferdinand.livejournal.com]

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 элементов, а в другом меньше. Потом просто рекусивно искать.

[whichferdinand.livejournal.com]

"Дальше просто переписать эти эелемнты , отсортировать, и найти нужный."

Ой, не получится, все равно их слишком много.

[vieni.livejournal.com]

Можно начать их сортировать, передвигая каждый элемент на то место, на котором он по порядку должен находиться. Есть число=5, то на 5е месте, а то число, которое было на пятом месте - опять же на его место. Остановимся, если какой-то элемент уже окажется на своем месте.

[avva.livejournal.com]

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

[dmage-ru.livejournal.com]

http://www.everfall.com/paste/id.php?5lhydzgs5tt4
вроде получилось O(n) времени и O(1) места :)

[avva.livejournal.com]

Браво! Простой и понятный код, люблю Питон :) Все верно!

[oulenspiegel.livejournal.com]

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;

[avva.livejournal.com]

"Поксорить все" решает некую задачу. Но это не эта задача :)

Вы упустили то, что не все числа от 1 до N-1 должны быть в массиве, повторов может быть много разных.

[pilpilon.livejournal.com]

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

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

[avva.livejournal.com]

Да, все верно!

[oulenspiegel.livejournal.com]

блин, дурь написал)

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];
}

[avva.livejournal.com]

Это изменяет массив и пользуется O(N) места - с таким же успехом можно этот подсчет делать в отдельном массиве.

[bespechnoepero.livejournal.com]

Первое число отнимается от второго. Если получается ноль, то задача решена, а если нет, то результат запоминается как число К. Далее, первое число минусуется от всех остальных, какждый раз результат сравнивается с ноль и с К. Если совпал, то задача решена, если нет, то переходим к следующему циклу, в котором все начинается от второго числа. И так далее, пока не найдем или ноль или К.

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

[meshko.livejournal.com]

Тут время O(n^2), а трюк с вычитанием ничего не дает на самом деле, все равно что сравнить каждое число с каждым.

[alaev.livejournal.com]

Вопрос о правилах подсчёта: если N очень велико, то для хранения одного числа нужно O(log(N)) места, то есть весь массив займет O(N*log(N)) места. То же самое касается, например, сравнения двух чисел: если они очень большие, то понять, равны ли они, можно только за O(log(N)) шагов. Учитывается ли это в Ваших оценках?

Или же мы считаем, что числа невелики, заведомо влезают в какой-нибудь регистр, и все операции занимают один шаг?

[avva.livejournal.com]

Обычно в таких задачах придерживаются среднего пути: с одной стороны, считаем, что все числа достаточно невелики, влезают в регистр, и обычные операции между ними занимают один шаг; с другой стороны, если в ходе алгоритма нужно повторить отдельно и по-разному какой-то шаг для каждого разряда числа (например, какая-то побитовая обработка), то это считается множителем logN, а не константным.

Тут есть определенное противоречие, но на практике это неплохо работает.

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

[bespechnoepero.livejournal.com]

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

Если же в в массиве есть повторяющиеся числа, то, по крайней мере, два числа в конечном массиве будут отличаться от суммы Е (или факториала F). Далее уже просто.

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

[bespechnoepero.livejournal.com]

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

[cryinstone.livejournal.com]

Используем сумму арифметической прогрессии
Time: O(N)
Space: O(1)

[avva.livejournal.com]

Нет, вы неправильно поняли условие.

[(Anonymous)]

Для начала возьмем 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;

[avva.livejournal.com]

return M;

Да, все правильно. Поздравляю! :)

[mad-ghost.livejournal.com]

Я наверняка очень плохой программист :( Но я не знаю проще чем:
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 заполняется до первого найденного повторяющегося числа.

[kapla55.livejournal.com]

Рассмотрим граф вершинами которого являются числа от 1 до N. Если в нашем массиве А[k] = j, то будем считать что в графе имется дуга из узла k в узел j. Очевидно, что часть узлов будет иметь больше одной входящей дуги и все узлы будут иметь как минимум одну исходящую дугу. Две входящие дуги в один узел будут соответствовать одинаковым числам в исходном массиве и такой узел обязан быть частью нетривиального цикла на графе. Найти цикла на графе можно с помощью двух бегущих указателей один в два раза быстрее другого. После этого пройдясь еще раз по цепочке найдем узел с двумя входными дугами.

Итого не более 4 раз проходим по массиву и используем О(1) дополнительной памяти (два указателя).

[meshko.livejournal.com]

tak a kak najti uzel s 2 vhodnymi dugami?

[sascha (from livejournal.com)]

Отличная перефразировка задачи о поиске начала цикла в односвязном списке, долго думал. :)
(структура списка: i -> a[i], начинаем из N, чтобы не попасть в цикл сразу, идём двумя итераторами, ну Вы эту задачу наверняка знаете)

Расскажите, плз, скрытым комментарием, как делать за O(N log N) и O(1) памяти? Ничего естественного в голову не приходит :)

[avva.livejournal.com]

Вот кто-то уже написал за меня, как делать за O(Nlog(N)) времени и O(1) места:

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

[avva.livejournal.com]

за O(N) :)

[igort75.livejournal.com]

ja beru pervoe chislo dopustim k,
stavlju ego na mesto k, beru to cheslo kotoroe bylo na meste k dopustem j
i stavlju ego na mesto j, i tak dalee
esle na meste k_j uzhe sidid k_j znachit konec poiska

[vieni.livejournal.com]

Мне кажется, как-то так и надо, только не менять элементы массива, а найти цикл и из этого цикла уже найти то число, которое повторяется. Под переменные там пойдет больше, чем 1, конечно... Но какая-то маленькая константа.