Dana jest tablica A[0..n] zawierająca liczby {1..n}. Napisz algorytm, który znajdzie dowolną liczbę występującą w tablicy więcej niż raz. Algorytm powinien działać w czasie liniowym i zużywać jedynie stałą ilość dodatkowej pamięci.
Kandydat: Czy można modyfikować tablicę wejściową?
Rekruter: Nie.
Zadanie to pojawia się czasem na rozmowach kwalifikacyjnych w pewnej firmie (kod trzydzieści trzy – dziesięć), choć generalnie nie powinno się go tu stosować. Dobre zadanie rekrutacyjne powinno mieć wiele możliwych rozwiązań i powinno sprawdzać umiejętność rozwiązywania problemów. To zadanie z kolei sprawdza jedynie wiedzę. Albo kandydat zna algorytm o który pyta rekruter, albo go nie zna i na rozmowie kwalifikacyjnej raczej go nie wymyśli. Algorytm jest ciekawy, a zatem warty przedstawienia go tutaj i ma praktyczne zastosowanie m.in. w algorytmie rho Pollarda.
Zacznijmy od kilku prostych obserwacji:
- W tablicy wejściowej musi istnieć liczba, która występuje dwukrotnie.
- A[0] ≠ 0
Utwórzmy graf, którego wierzchołkami będą liczby {0, 1, …, n}. Jeżeli A[u] = v to w naszym grafie wstawiamy krawędź skierowaną z wierzchołka u do wierzchołka v. Nasz graf ma następujące własności:
- Graf jest zbiorem cykli z dołączonymi do niego drzewami
- Wierzchołek 0 jest częścią drzewa (a nie cyklu)
- Każdy wierzchołek cyklu do którego doczepione jest drzewo ma numer, który występuje co najmniej dwukrotnie w tablicy wejściowej (bo jego stopień wejściowy wynosi co najmniej 2: prowadzi do niego jeden wierzchołek z cyklu i co najmniej jeden wierzchołek z drzewa).
Ideą algorytmu jest rozpoczęcie od wierzchołka 0 (należącego do drzewa) i znalezienie na ścieżce od niego, pierwszego wierzchołka występującego w cyklu (na rysunku jest to wierzchołek 2). Numer wierzchołka zwracamy jako wynik działania algorytmu.
Algorytm, który przedstawię idzie po grafie dwoma wskaźnikami. Jeden z nich w każdym obrocie pętli będzie przesuwał się o jeden wierzchołek (żółw), a drugi będzie przesuwał się o dwa wierzchołki (zając). Pętlę kończymy, gdy oba wskaźniki będą wskazywały ten sam wierzchołek. Oznaczać to będzie, że zarówno żółw jak i zając znajdują się na cyklu. Zacznijmy od udowodnienia, że nasz algorytm się nie zapętla i działa w czasie liniowym:
Lemat. Zając spotka się z żółwiem i nastąpi to szybciej niż żółw zdąży okrążyć cały cykl.
Dowód. Rozważmy moment w którym żółw po raz pierwszy znalazł się na cyklu. Niech L oznacza długość cyklu. Przenumerujmy wierzchołki na cyklu liczbami od 0 do L-1 w ten sposób aby zając znalazł się na pozycji 0. Oznaczmy pozycję żółwia jako p. Po p iteracjach pętli, zarówno zając jak i żółw znajdą się na wierzchołku z numerem 2 * p (mod L), co kończy dowód.
Znaleźliśmy cykl. Musimy jeszcze znaleźć pierwszy wierzchołek na cyklu. Pomoże nam w tym celu drugi lemat.
Lemat. Niech x oznacza długość ścieżki od wierzchołka zero do pierwszego wierzchołka na cyklu; p oznacza liczbę kroków od wejścia żółwia na cykl do spotkania zająca; L oznacza długość cyklu i niech z = L – p. Wtedy zachodzi x mod L = z.
Dowód. Żółw przeszedł x + p wierzchołków. W tym czasie zając musiał przejść 2(x + p) wierzchołków. Najpierw zając przeszedł drogę do cyklu o długości x, a następnie mógł przejść kilkukrotnie cykl, aby skończyć na wierzchołku oddalonym o p od pierwszego wierzchołka na cyklu:
2(x + p) = x + kL + p
gdzie k ≥ 1 oznacza liczbę okrążeń cyklu przez zająca. Odejmując obustronnie x + p i przenosząc p na drugą stronę, otrzymujemy:
x = kL – p = (k – 1)L + L – p = (k – 1)L + z
co kończy nasz dowód.
W jaki sposób pomaga to naszemu algorytmowi znaleźć punkt wejścia do pętli? Żółw i zając spotkali się w punkcie p. Jeśli teraz puścilibyśmy z punktu 0 drugiego żółwia, to po dojściu do cyklu spotkałby on pierwszego żółwia. Drugi żółw przeszedłby x wierzchołków, zatem również pierwszy musiałby tyle przejść. Ale ponieważ x mod L = z to pierwszy żółw startując z pozycji p, musi się znaleźć na wejściu do cyklu po przejściu (k-1)L + z kroków.
Finalnie nasz algorytm wygląda następująco:
int znajdzDuplikat(const vector<int>& A)
{
int zolw = 0;
int zajac = 0;
do
{
zolw = A[zolw];
zajac = A[A[zajac]];
} while (zolw != zajac);
int drugi_zolw = 0;
do
{
zolw = A[zolw];
drugi_zolw = A[drugi_zolw];
} while (drugi_zolw != zolw);
return zolw;
}Pierwsza pętla do while wykonuje x + p kroków o czym mówi nam pierwszy z lematów. Druga pętla wykonuje x kroków, zatem całość działa w czasie O(n) w najgorszym przypadku. Algorytm używa jedynie trzech dodatkowych zmiennych, zatem jego złożoność pamięciowa to O(1).
Algorytm nazywa się algorytmem Floyda, ale “algorytm żółwia i zająca” wydawał mi się bardziej chwytliwym tytułem.
Jeśli ktoś nie znał tego algorytmu i dał radę wymyślić go podczas rozmowy kwalifikacyjnej, to niech da znać. Bardzo chciałbym go poznać!
