Longest Consecutive Sequence
Otrzymujesz tablicę liczb całkowitych nums w dowolnej kolejności. Sekwencja kolejnych liczb to grupa wartości x, x+1, x+2 i tak dalej, z których każda występuje gdzieś w nums. Zwróć długość najdłuższej sekwencji kolejnych liczb. Wartość, która występuje więcej niż raz, jest liczona tylko raz.
Funkcja
- numsinteger-array
- liczby całkowite, w dowolnej kolejności, powtórzenia dozwolone
- Zwracainteger
- długość najdłuższego ciągu kolejnych wartości występujących w nums
Ograniczenia
1 ≤ nums.length ≤ 104-109 ≤ nums[i] ≤ 109- Wartości mogą się powtarzać. Pozycje w tablicy nie mają znaczenia, liczy się tylko to, które wartości występują.
Przykłady
- Wejście
- nums = [40, 4, 39, 1, 3, 2, 41]
- Wyjście
- 4
- Wyjaśnienie
1,2,3i4są obecne — tworzą serię 4 kolejnych liczb, mimo że są rozrzucone w tablicy. Druga seria, od39do41, zawiera tylko 3 wartości.
- Wejście
- nums = [7, 3, 7, 5, 6, 5]
- Wyjście
- 3
- Wyjaśnienie
5,6i7tworzą ciąg 3 liczb. Drugie7i drugie5niczego nie dodają, a3nie może dołączyć, ponieważ brakuje4.
- Wejście
- nums = [10, 30, 20]
- Wyjście
- 1
- Wyjaśnienie
- Żadne dwie wartości nie różnią się o 1, więc każdy ciąg zawiera jedną wartość, a odpowiedź to 1.
+17 ukrytych testów przy wysłaniu
Pytanie dodatkowe
Załóżmy, że wartości napływają pojedynczo i po każdej z nich musisz podać długość najdłuższej serii do tej pory. Czy potrafisz aktualizować odpowiedź w średnim czasie O(1) dla każdej wartości?
Podpowiedzi
Otwieraj je po kolei. Każda zdradza trochę więcej.
Wypróbuj każdą wartość jako pierwszą liczbę w sekwencji i licz w górę. Jakie pytanie zadajesz raz za razem i jaki jest koszt każdej odpowiedzi, gdy szukasz jej w tablicy?
Pytanie brzmi: „czy
x+1znajduje się w tablicy?”. Zbiór haszujący odpowiada na nie w stałym czasie (średnio) i usuwa też powtórzenia.Zacznij liczyć tylko od wartości
x, której poprzednikax-1brakuje w zbiorze. Następnie przechodź dox+1,x+2i kolejnych wartości, dopóki znajdują się w zbiorze, i zachowaj najdłuższy ciąg. Każda wartość zostanie wtedy odwiedzona tylko w jednym ciągu.
Rozwiązanie
Wartości ciągu mogą znajdować się w dowolnym miejscu tablicy, więc nie można odczytywać kolejnych elementów ciągu od lewej do prawej. Sortowanie układa je w czasie O(n log n). Zbiór haszujący działa lepiej: odpowiada na pytanie „czy x+1 jest tutaj?” w czasie O(1), a jeśli liczenie zaczynasz tylko od wartości, dla których brakuje x-1, każda wartość jest odwiedzana raz, co sprawia, że całe wyszukiwanie ma złożoność O(n).
Zwiększaj licznik od każdej wartości, przeszukując tablicę
Poprawne, ale nie kończy się na największych testach
Intuicja
Potraktuj każdą wartość jako możliwy początek ciągu. Dla x wyszukaj w tablicy x+1; jeśli tam jest, wyszukaj x+2 i kontynuuj, aż zabraknie jakiejś wartości. Liczba znalezionych wartości to długość ciągu zaczynającego się od x, a odpowiedzią jest największa z tych długości.
To poprawne, ponieważ każdy ciąg ma najmniejszą wartość, ta wartość znajduje się w nums, a pętla sprawdza ją jako początek i przechodzi przez cały ciąg. Powtórzenia nie szkodzą: jedynie sprawiają, że ten sam początek jest sprawdzany dwa razy.
To rozwiązanie jest powolne z dwóch powodów. Każde sprawdzenie „czy ta wartość tu jest?” odczytuje maksymalnie n wartości, a długi ciąg jest przechodzony ponownie od każdego z jego elementów. Weźmy 10^4 wartości tworzących jeden przemieszany ciąg: łączna liczba kroków tych przejść wynosi około n²/2 = 5 × 10^7, a każdy krok skanuje średnio połowę tablicy. To około 2.5 × 10^11 porównań.
Algorytm
- Ustaw
bestna 0. - Dla każdej wartości
startwnumsustawcurrentnastart, alengthna 1. - Gdy przeszukiwanie
numsznajdziecurrent+1, zwiększcurrentilengtho 1. - Zapisz
lengthwbest, jeśli jest większa. - Zwróć
best.
def longestConsecutive(nums):
best = 0
for start in nums:
current = start
length = 1
# "in" on a list reads it from the front until it finds the value.
while current + 1 in nums:
current += 1
length += 1
best = max(best, length)
return bestPosortuj, a następnie policz serie
Intuicja
Sortowanie umieszcza obok siebie wartości należące do każdej serii. [40, 4, 39, 1, 3, 2, 41] zmienia się w [1, 2, 3, 4, 39, 40, 41], a serie odczytujemy od lewej do prawej: od 1 do 4, a potem przeskok do 39.
Przejdź po posortowanych wartościach i śledź długość bieżącej serii. Wartość większa o jeden od poprzedniej wydłuża ją. Wartość równa poprzedniej jest powtórzeniem: pomiń ją, bo ani nie wydłuża serii, ani jej nie kończy. Każda inna wartość oznacza lukę i rozpoczyna nową serię o długości 1.
Sortowanie kosztuje O(n log n), a przejście po wartościach O(n). Sortowanie w miejscu nie wymaga dodatkowej tablicy, ale zmienia kolejność danych wejściowych przekazanych przez wywołującego; języki, które sortują kopię, zużywają O(n) pamięci.
Algorytm
- Posortuj
numsrosnąco. - Ustaw
bestirunna 1, ponieważ tablica nigdy nie jest pusta. - Dla każdego indeksu
izaczynając od 1, pomińnums[i], jeśli jest równynums[i-1]. - Jeśli
nums[i]jest równenums[i-1]+1, dodaj 1 dorun; w przeciwnym razie ustawrunna 1. Zapiszrunwbest, jeśli jest większe. - Zwróć
best.
def longestConsecutive(nums):
nums.sort()
best = 1
run = 1
for i in range(1, len(nums)):
if nums[i] == nums[i - 1]:
continue # a repeat neither extends nor breaks the run
if nums[i] == nums[i - 1] + 1:
run += 1
else:
run = 1
best = max(best, run)
return bestZbiór haszujący, zliczający tylko od początku każdego przebiegu
Intuicja
Umieść każdą wartość w zbiorze haszującym. Teraz sprawdzenie „czy x+1 jest obecne?” kosztuje średnio O(1) zamiast skanowania, a powtórzenia scalają się w jeden wpis.
Przechodzenie od każdej wartości nadal powodowałoby powtarzanie pracy: w ciągu 1, 2, 3, 4 wykonasz 3 kroki od 1, 2 od 2 i 1 od 3. Zacznij więc przejście tylko od pierwszej wartości ciągu. Wartość x jest pierwsza dokładnie wtedy, gdy x-1 nie należy do zbioru. W [40, 4, 39, 1, 3, 2, 41] kwalifikują się tylko 1 i 39: od 1 docierasz do 4, co daje długość 4, a od 39 docierasz do 41, co daje długość 3.
Każda wartość należy dokładnie do jednego ciągu i tylko przejście od pierwszej wartości tego ciągu wykonuje krok, przechodząc przez nią, więc wszystkie przejścia łącznie wymagają najwyżej n kroków. Dodaj jedno sprawdzenie przynależności dla każdej wartości i utworzenie zbioru, a łączny czas wyniesie O(n), przy użyciu O(n) pamięci na zbiór.
Iteruj po zbiorze, a nie po nums. Jeśli pierwsza wartość ciągu o długości 2,500 występuje w nums 2,000 razy, iterowanie po nums spowoduje przejście przez ten ciąg 2,000 razy.
Algorytm
- Umieść każdą wartość z
numsw zbiorze haszującymvaluesi ustawbestna 0. - Dla każdej wartości
xw zbiorze pomiń ją, jeślix-1znajduje się w zbiorze: nie jest pierwszą wartością w swoim ciągu. - W przeciwnym razie ustaw
endnaxi zwiększaj je o 1, dopókiend+1znajduje się w zbiorze. - Zapisz
end-x+1wbest, jeśli jest większe. - Zwróć
best.
def longestConsecutive(nums):
values = set(nums)
best = 0
for value in values:
# Only a value with no left neighbour starts a run.
if value - 1 in values:
continue
end = value
while end + 1 in values:
end += 1
best = max(best, end - value + 1)
return best
Pułapki i przypadki brzegowe
Większość błędnych odpowiedzi wynika z powtarzających się wartości, a większość wolnych odpowiedzi — z przechodzenia przez ten sam ciąg więcej niż raz.
- Traktowanie powtórzenia jak przerwy lub kroku po sortowaniu. W
[1, 2, 2, 3]zresetowanie ciągu przy drugim2daje 2, a policzenie go jako kroku daje 4. Odpowiedź to 3. - Ustawienie
bestna 0 podczas przechodzenia po posortowanych wartościach i aktualizowanie go tylko wewnątrz pętli. Tablica zawierająca jedną wartość zwróci wtedy 0 zamiast 1. - Przechodzenie od każdej wartości ze zbioru zamiast tylko od początku ciągu. Odpowiedź jest poprawna, ale przejście przez jeden ciąg zawierający
10^4wartości wymaga5 × 10^7kroków — to złożoność kwadratowa, której miało zapobiec użycie zbioru. - Iterowanie po
numszamiast po zbiorze, gdy wartości się powtarzają. Ciąg zaczynający się od wartości występującej tysiące razy jest przechodzony tysiące razy. - Oznaczanie wartości w tablicy indeksowanej wartością. Wartości sięgają
±10^9, więc tablica musiałaby zawierać2 × 10^9elementów.
Najczęstsze pytania4
Czym jest złożoność czasowa problemu najdłuższego ciągu kolejnych liczb?
Rozwiązanie z użyciem zbioru haszującego działa średnio w czasie O(n) i wykorzystuje dodatkową pamięć O(n). Sortowanie, a następnie zliczanie serii zajmuje O(n log n). Wyszukiwanie w tablicy kolejnej wartości bez użycia zbioru może zająć nawet O(n³).
Dlaczego rozwiązanie z użyciem zbioru mieszającego ma złożoność O(n), skoro w pętli for znajduje się pętla while?
Pętla wewnętrzna uruchamia się tylko dla wartości, której lewego sąsiada x-1 brakuje, czyli dla pierwszej wartości w jej ciągu. Każda wartość jest pomijana podczas przejścia przez jej własny ciąg i przez żadne inne przejście, więc wszystkie pętle wewnętrzne łącznie wykonują co najwyżej n kroków. Pętla zewnętrzna dodaje jedno sprawdzenie dla każdej wartości, co daje łącznie O(n).
Czy potrafisz rozwiązać problem najdłuższego ciągu kolejnych liczb bez dodatkowej pamięci?
Tak, jeśli możesz zmienić kolejność danych wejściowych: posortuj je w miejscu i policz serie w jednym przebiegu, pomijając powtórzenia. To wymaga dodatkowej pamięci O(1), ale czasu O(n log n). Rozwiązanie O(n) wymaga zbioru haszującego.
Czy struktura union-find może rozwiązać problem najdłuższego ciągu kolejnych liczb?
Tak. Utwórz zbiór dla każdej odrębnej wartości, połącz x z x+1, gdy obie wartości są obecne, i zwróć rozmiar największego zbioru. Działa w czasie bliskim O(n), ale wymaga mapy wartości na indeks, powiązań rodziców i rozmiarów, podczas gdy przejście po zbiorze haszującym wykonuje to samo zadanie za pomocą jednego zbioru i dwóch pętli.
Podobne zadania
Zadania oparte na tych samych pomysłach. Rozwiązanie dwóch lub trzech utrwala schemat.
Python
def longestConsecutive(nums):
# Wpisz kod tutajPrzypadek 1
Przypadek 2
Przypadek 3
Wejście
nums = [40, 4, 39, 1, 3, 2, 41]
Oczekiwane
4