Find the Duplicate Number
Otrzymujesz tablicę nums zawierającą n+1 liczb całkowitych, z których każda mieści się w przedziale od 1 do n. Dokładnie jedna wartość występuje więcej niż raz, być może wiele razy, i zwracasz tę wartość.
Rozwiąż to bez zmieniania nums i używając tylko stałej ilości dodatkowej pamięci.
Funkcja
- numsinteger-array
- n+1 liczb całkowitych, z których każda mieści się w przedziale od 1 do n
- Zwracainteger
- wartość, która pojawia się więcej niż raz
Ograniczenia
1 ≤ n ≤ 104nums.length == n+11 ≤ nums[i] ≤ n- Dokładnie jedna wartość występuje co najmniej dwa razy; każda pozostała wartość występuje najwyżej raz.
Przykłady
- Wejście
- nums = [2, 5, 1, 3, 5, 4]
- Wyjście
- 5
- Wyjaśnienie
- Tutaj
nwynosi 5, a 5 znajduje się na pozycjach 1 i 4, więc odpowiedzią jest 5. Każda inna wartość od 1 do 5 występuje raz.
- Wejście
- nums = [4, 2, 4, 1, 4]
- Wyjście
- 4
- Wyjaśnienie
- 4 występuje trzy razy, na pozycjach 0, 2 i 4, a 3 nie występuje wcale. Powtórzenie może zastąpić kilka brakujących wartości, więc odpowiedzią jest 4.
+17 ukrytych testów przy wysłaniu
Pytanie dodatkowe
Wyszukiwanie binarne po wartościach pozwala zachować obie reguły w czasie O(n log n). Czy potrafisz zachować je w czasie O(n)?
Podpowiedzi
Otwieraj je po kolei. Każda zdradza trochę więcej.
Każda wartość mieści się w przedziale od 1 do
n, a tablica ma pozycje od 0 don. Zatem każda wartość jest też prawidłową pozycją. Zacznij na pozycji 0, przejdź do pozycjinums[0], potem do pozycji wskazanej przez tę wartość i tak dalej. Co musi się stać z takim przechodzeniem?Spacer nigdy się nie kończy i ma tylko
n+1pozycji do odwiedzenia, więc wpada w pętlę. Pozycja, w której wchodzi w pętlę, jest osiągana z dwóch różnych pozycji, a obie mają tę pozycję jako swoją wartość.Znajdź wejście do pętli za pomocą dwóch wskaźników rozpoczynających z pozycji 0: jeden przeskakuje raz na rundę, a drugi dwa razy, aż znajdą się na tej samej pozycji. Następnie cofnij jeden z nich na pozycję 0 i przesuwaj oba o jeden skok naraz. Spotkają się przy wejściu, które jest odpowiedzią.
Rozwiązanie
Zbiór haszujący lub sortowanie pozwala od razu znaleźć powtórzenie, ale oba sposoby łamią zasady: zbiór wymaga pamięci na każdą wartość, a sortowanie zmienia nums. Rozwiązanie kryje się w liczbach. Każda wartość mieści się w przedziale od 1 do n, więc jest też prawidłową pozycją w tablicy. Odczytuj każdą wartość jako odnośnik do innej pozycji, a podążanie za odnośnikami od pozycji 0 zawsze kończy się w pętli, której wejściem jest duplikat. Szybkie i wolne wskaźniki Floyda znajdują to wejście za pomocą dwóch liczb całkowitych.
Porównaj każdą parę
Poprawne, ale nie kończy się na największych testach
Intuicja
Powtarzająca się wartość znajduje się na co najmniej dwóch pozycjach i < j. Porównaj każdą pozycję z każdą kolejną; pierwsza para równych wartości daje odpowiedź. W pierwszym przykładzie na pozycji 1 znajduje się 5, a skanowanie od pozycji 2 wzwyż znajduje kolejną 5 na pozycji 4.
Dzięki temu spełnione są obie zasady: nic nie jest zapisywane, a jedyną pamięcią są dwa liczniki pętli. To wolne rozwiązanie, ponieważ porównuje pary. Przy n+1 = 10,001 wartościach, gdy obie kopie znajdują się blisko końca, sprawdza około 5 × 10^7 par.
Algorytm
- Dla każdej pozycji
iod 0 do końca: - Dla każdej pozycji
jpoiporównajnums[i]znums[j]. - Zwróć
nums[i]przy pierwszym dopasowaniu.
def findDuplicate(nums):
n = len(nums)
for i in range(n):
for j in range(i + 1, n):
if nums[i] == nums[j]:
return nums[i]
return -1 # unreachable: the input always holds a repeatWyszukiwanie binarne wartości
Intuicja
Przeszukuj zakres wartości, a nie pozycji. Wybierz próg m i policz, ile elementów nums jest nie większych niż m.
Jeśli duplikat d jest większy niż m, wartości od 1 do m występują najwyżej raz każda, więc liczba wynosi najwyżej m. Jeśli d jest nie większe niż m, każda wartość większa niż m występuje najwyżej raz, więc najwyżej n-m elementów jest większych niż m, a co najmniej m+1 jest nie większych niż m. Zatem test „count > m” jest fałszywy dla każdego m mniejszego niż d i prawdziwy od d wzwyż. Wyszukiwanie binarne znajduje pierwsze m, dla którego test staje się prawdziwy, a jest nim d.
W drugim przykładzie n wynosi 4. Dla m = 2 elementy 2 i 1 dają wynik 2, a nie więcej niż 2, więc odpowiedź jest większa niż 2. Dla m = 3 wynik nadal wynosi 2, więc odpowiedzią jest 4. Każda runda odczytuje całą tablicę raz i zmniejsza zakres o połowę, więc złożoność wynosi O(n log n): około 14 przebiegów po 10,001 wartościach.
Algorytm
- Ustaw
low= 1 ihigh=n, czyli długośćnumspomniejszoną o jeden. - Gdy
low < high, wyznaczmidw połowie między nimi. - Policz elementy
nums, które są nie większe niżmid. - Jeśli liczba jest większa niż
mid, ustawhigh=mid; w przeciwnym razie ustawlow=mid+1. - Zwróć
low.
def findDuplicate(nums):
low, high = 1, len(nums) - 1
while low < high:
mid = (low + high) // 2
# How many values fall in 1..mid?
count = 0
for x in nums:
if x <= mid:
count += 1
if count > mid:
high = mid # 1..mid holds more values than it has room for
else:
low = mid + 1 # the repeat is above mid
return lowWykrywanie cyklu Floyda w łączach wartości
Intuicja
Odczytaj tablicę jako połączenia: pozycja i wskazuje pozycję nums[i]. Każda pozycja od 0 do n ma dokładnie jedno połączenie wychodzące, a każde połączenie prowadzi do pozycji od 1 do n. W pierwszym przykładzie połączenia to: 0 → 2, 1 → 5, 2 → 1, 3 → 3, 4 → 5 i 5 → 4.
Zacznij na pozycji 0 i podążaj za połączeniami. Wędrówka nigdy się nie zatrzyma, ponieważ z każdej pozycji prowadzi połączenie, a pozycji jest tylko n+1, więc musi wrócić do jednej z tych, które już odwiedziła. Od tego momentu będzie krążyć bez końca. Ścieżka składa się z ogona, po którym następuje pętla, i przypomina kształtem grecką literę ρ. W pierwszym przykładzie wędrówka przebiega przez pozycje 0, 2, 1, 5, 4, 5, 4 i tak dalej: ogon to 0, 2, 1, a pętla to 5, 4. Pozycja 3 wskazuje samą siebie, ale wędrówka nigdy do niej nie dociera, co nie stanowi problemu.
Wejście do pętli jest duplikatem. Wędrówka wchodzi na pozycję 5 dwa razy z różnych miejsc: raz z końca ogona (pozycji 1, ponieważ nums[1] wynosi 5) i raz z końca pętli (pozycji 4, ponieważ nums[4] wynosi 5). Dwie różne pozycje zawierają wartość 5, więc 5 się powtarza. Ogon zawsze zawiera pozycję 0, ponieważ żadna wartość nie wynosi 0 i żadne połączenie nigdy do niej nie prowadzi, więc do wejścia do pętli zawsze prowadzą te dwa różne połączenia. Powtarza się dokładnie jedna wartość, zatem wejście do pętli jest tą wartością.
Teraz znajdź wejście do pętli za pomocą dwóch wskaźników, tak jak przy wykrywaniu cyklu w liście wiązanej. W fazie 1 slow podąża o jedno połączenie w każdej turze, a fast o dwa, aż spotkają się na tej samej pozycji gdzieś w pętli. W pierwszym przykładzie spotykają się na pozycji 4. W fazie 2 umieść slow z powrotem na pozycji 0, pozostaw fast tam, gdzie jest, i przesuwaj oba wskaźniki o jedno połączenie w każdej turze. Spotkają się na wejściu do pętli.
Dlaczego działa faza 2: załóżmy, że przejście ogona do wejścia do pętli wymaga T połączeń, a pętla ma C pozycji. Gdy wskaźniki się spotkały, slow wykonał s kroków, a fast 2s. Oba znalazły się w tym samym miejscu, więc dodatkowe s kroków wskaźnika fast stanowiło całkowitą liczbę okrążeń pętli. Po kolejnych T krokach slow dociera do wejścia do pętli, idąc od pozycji 0, a fast znajduje się w miejscu, w którym znalazłaby się wędrówka od pozycji 0 po s+T krokach, ponieważ dodatkowe okrążenia niczego nie zmieniają. To T kroków do wejścia do pętli plus s kroków, czyli całkowita liczba okrążeń, co również umieszcza go na wejściu do pętli. Nie mogą spotkać się wcześniej, ponieważ slow wciąż znajduje się na ogonie, a fast nigdy nie opuszcza pętli. W pierwszym przykładzie slow przechodzi przez pozycje 2, 1, 5, a fast przez 5, 4, 5; spotykają się na pozycji 5 po T = 3 krokach.
Każda faza wymaga O(n) kroków, jedyna używana pamięć to dwie pozycje, a tablica nums nigdy nie jest modyfikowana.
Algorytm
- Potraktuj każdą pozycję
ijako węzeł prowadzący do pozycjinums[i]i ustaw oba wskaźniki na pozycji 0. - Faza 1: przesuwaj
slowdonums[slow], afastdonums[nums[fast]], aż będą równe. - Faza 2: ustaw
slowz powrotem na 0. - Przesuwaj oba wskaźniki o jedno ogniwo naraz:
slowdonums[slow], afastdonums[fast], aż będą równe. - Zwróć tę pozycję: to powtarzająca się wartość.
def findDuplicate(nums):
# Treat each index i as a node with one link, to nums[i].
# Phase 1: slow moves one link, fast moves two, until they meet in the cycle.
slow = fast = 0
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
# Phase 2: restart one pointer at index 0 and move both one link at a time.
# They meet at the cycle's entrance, the index two positions link to.
slow = 0
while slow != fast:
slow = nums[slow]
fast = nums[fast]
return slow
Pułapki i przypadki brzegowe
Większość błędnych odpowiedzi wynika z mylenia pozycji z wartościami albo z zakończenia metody Floyda o jeden etap za wcześnie.
- Zwrócenie punktu spotkania z etapu 1. To jakaś pozycja w pętli, niekoniecznie jej początek. W pierwszym przykładzie wskaźniki spotykają się na pozycji 4, ale odpowiedzią jest 5.
- Sprawdzanie
slow == fastprzed pierwszym ruchem. Oba wskaźniki zaczynają na pozycji 0, więc pętla kończy się od razu. Najpierw wykonaj ruch, a potem porównaj, albo ustaw wskaźniki odpowiednio jedno i dwa ogniwa dalej. - Rozpoczęcie przejścia z dowolnego miejsca poza pozycją 0. Żadne ogniwo nie wskazuje pozycji 0, ponieważ żadna wartość nie wynosi 0, a to gwarantuje istnienie ogona. Rozpoczęcie z innej pozycji może umieścić cię w pętli, do której nie da się wejść z zewnątrz, jak pozycja 3 w pierwszym przykładzie, której wejście niczego nie dowodzi.
- Zakładanie, że duplikat występuje dokładnie dwa razy. Sztuczka z sumą, suma minus
1 + 2 + ... + n, daje 15 minus 10 = 5 w drugim przykładzie, ale odpowiedzią jest 4. To samo dotyczy sztuczek z XOR. - Wyszukiwanie binarne po pozycjach zamiast po wartościach albo sprawdzanie
count >= mid. Liczba wartości nie większych niżmwynosi dokładniem, gdy żadna wartość od 1 domsię nie powtarza i żadnej nie brakuje, więc tylko>pozwala rozróżnić obie strony. - Oznaczanie odwiedzonych wartości przez zmianę znaku
nums[x]albo zamienianie wartości miejscami. Oba sposoby działają, ale oba zmieniają tablicę, czego zadanie zabrania.
Najczęstsze pytania4
Jaka jest złożoność czasowa zadania „Znajdź powtarzającą się liczbę”?
Wykrywanie cykli Floyda działa w czasie O(n) i wymaga O(1) dodatkowej pamięci: każda z dwóch faz przechodzi co najwyżej kilka wielokrotności n łączy. Wyszukiwanie binarne wartości zajmuje O(n log n) czasu i O(1) pamięci. Porównanie każdej pary ma złożoność O(n²).
Dlaczego algorytm wykrywania cyklu Floyda znajduje zduplikowaną liczbę?
Jeśli odczytasz każdą wartość jako połączenie pozycji, na której się znajduje, z pozycją, którą wskazuje, przejście od pozycji 0 musi zakończyć się w pętli, ponieważ nigdy się nie zatrzymuje i ma do przejścia tylko n+1 miejsc. Do pozycji, w której wchodzi w pętlę, prowadzą dwie różne pozycje: jedna na ogonie, a druga w pętli, więc dwie pozycje zawierają tę wartość. Metoda Floyda znajduje wejście do pętli za pomocą dwóch wskaźników, dlatego znajduje powtarzającą się wartość.
Dlaczego nie użyć zbioru haszującego albo posortować tablicy?
Oba rozwiązania znajdują odpowiedź w czasie O(n) lub O(n log n), a w prawdziwym programie każde z nich byłoby w porządku. Zadanie celowo ich zabrania: zbiór haszujący zużywa dodatkową pamięć O(n), a sortowanie albo zmienia nums, albo wymaga utworzenia pełnej kopii. To właśnie ograniczenia skłaniają cię do spojrzenia na problem z perspektywy cyklu.
Dlaczego wzór na sumę nie działa w zadaniu „Znajdź zduplikowaną liczbę”?
Odjęcie 1 + 2 + ... + n od sumy tablicy daje wartość duplikatu tylko wtedy, gdy występuje on dokładnie dwa razy, a każda inna wartość występuje raz. W tym przypadku powtarzająca się wartość może występować wiele razy i zastępować brakujące wartości. W [4, 2, 4, 1, 4] różnica wynosi 15 minus 10 = 5, a tej liczby nie ma nawet w tablicy.
Podobne zadania
Zadania oparte na tych samych pomysłach. Rozwiązanie dwóch lub trzech utrwala schemat.
Python
def findDuplicate(nums):
# Napisz kod tutajPrzypadek 1
Przypadek 2
Wejście
nums = [2, 5, 1, 3, 5, 4]
Oczekiwane
5