Longest Consecutive Sequence
Otrzymujesz tablicę liczb całkowitych nums w dowolnej kolejności. Ciąg 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ższego ciągu kolejnych liczb. Wartość występująca 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ższej serii 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 w niej występują.
Przykłady
- Wejście
- nums = [40, 4, 39, 1, 3, 2, 41]
- Wyjście
- 4
- Wyjaśnienie
1,2,3i4są obecne, tworząc serię 4 wartości, mimo że są rozproszone 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 o długości 3. 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 pojedynczą wartość, a odpowiedź wynosi 1.
Pytanie dodatkowe
Załóżmy, że wartości napływają pojedynczo i po każdej z nich musisz podać najdłuższą serię do tej pory. Czy potrafisz na bieżąco aktualizować odpowiedź w średnim czasie O(1) na każdą wartość?
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ę. Które pytanie zadajesz w kółko 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 średnim czasie stałym, a także usuwa powtórzenia.Zacznij liczenie tylko od wartości
x, którejx-1nie ma 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 serii mogą znajdować się w dowolnym miejscu tablicy. Sortowanie układa je w O(n log n). Zbiór haszujący odpowiada na pytanie „czy jest tu x+1?” w O(1), a jeśli liczysz tylko od wartości, dla których brakuje x-1, każda wartość jest odwiedzana raz: łącznie O(n).
Policz w górę od każdej wartości, przeszukując tablicę
Poprawne, ale nie kończy się na największych testach
Intuicja
Traktuj każdą wartość jako możliwy początek ciągu. Zaczynając od x, szukaj w tablicy x+1, następnie x+2, aż zabraknie jakiejś wartości, i zachowaj największą długość. Każdy ciąg ma najmniejszą wartość w nums, a pętla przechodzi od niej przez cały ciąg.
Każde wyszukiwanie sprawdza do n wartości, a długi ciąg jest ponownie przechodzony od każdego jego elementu. W przypadku 10^4 wartości tworzących jeden potasowany ciąg przejścia wymagają około n²/2 = 5 × 10^7 kroków, z których każdy średnio skanuje połowę tablicy: około 2.5 × 10^11 porównań.
Algorytm
- Ustaw
bestna 0. - Dla każdej wartości
startwnumsustawcurrentnastart, alengthna 1. - Gdy podczas przeszukiwania
numszostanie znalezionecurrent+1, zwiększcurrentilengtho 1. - Zapisz
lengthwbest, jeśli jest większe. - 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 bestSortuj, a następnie licz serie
Intuicja
Sortowanie umieszcza wartości z każdego ciągu obok siebie: [40, 4, 39, 1, 3, 2, 41] zmienia się w [1, 2, 3, 4, 39, 40, 41], a ciągi odczytuje się od lewej do prawej.
Przejdź po posortowanych wartościach i zachowuj długość bieżącego ciągu. Wartość o jeden większa od poprzedniej wydłuża go. Powtórzenie ani nie wydłuża ciągu, ani go nie kończy, więc je pomiń. Każda inna wartość rozpoczyna nowy ciąg o długości 1.
Sortowanie kosztuje O(n log n), a przejście O(n). Sortowanie w miejscu nie wymaga dodatkowej tablicy; języki, w których sortowanie tworzy 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ównenums[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, liczenie tylko od początku każdego uruchomienia
Intuicja
W przypadku każdej wartości w zbiorze haszującym sprawdzenie przynależności zajmuje średnio O(1), a powtórzenia sprowadzają się do jednego wpisu.
Przechodzenie od każdej wartości nadal oznaczałoby powtarzanie pracy: w ciągu 1, 2, 3, 4 wykonasz 3 kroki od 1, 2 od 2 i 1 od 3. Dlatego przechodź tylko od pierwszej wartości ciągu, czyli takiej wartości x, dla której brakuje x-1. W przykładzie 1 kwalifikują się tylko 1 i 39, co daje ciągi o długości 4 i 3.
Każda wartość należy do jednego ciągu i jest uwzględniana tylko podczas przejścia tego ciągu, więc wszystkie przejścia łącznie wykonują najwyżej n kroków. Przy jednym sprawdzeniu na wartość całkowita złożoność wynosi O(n) czasu, a pamięć zajmowana przez zbiór to O(n).
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 go o 1, dopókiend+1znajduje się w zbiorze. - Zapisz
end-x+1wbest, jeśli jest większa. - 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
- Traktowanie powtórzenia jako przerwy albo 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 posortowanej tablicy 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ątków ciągów. Przejście przez jeden ciąg o długości
10^4wartości wymaga wtedy5 × 10^7kroków. - Iterowanie po
numszamiast po zbiorze. Jeśli pierwsza wartość ciągu o długości 2,500 występuje 2,000 razy, ciąg jest przechodzony 2,000 razy. - Indeksowanie tablicy wartością. Wartości sięgają
±10^9, więc potrzeba2 × 10^9elementów.
Najczęstsze pytania3
Jaka jest złożoność czasowa problemu najdłuższego ciągu kolejnych liczb?
Rozwiązanie z użyciem zbioru mieszającego działa średnio w czasie O(n) i wymaga O(n) dodatkowej pamięci. Sortowanie i zliczanie serii zajmuje O(n log n). Wyszukiwanie w tablicy każdej kolejnej wartości bez użycia zbioru zajmuje do O(n³).
Czy potrafisz rozwiązać problem najdłuższego ciągu kolejnych elementów bez dodatkowej pamięci?
Tak, jeśli możesz zmienić kolejność danych wejściowych: posortuj je w miejscu i policz ciągi w jednym przebiegu, pomijając powtórzenia. Wymaga to dodatkowej pamięci O(1), ale czasu O(n log n). Rozwiązanie O(n) wymaga zbioru haszującego.
Czy union-find może rozwiązać problem najdłuższego kolejnego ciągu?
Tak. Utwórz zbiór dla każdej unikalnej wartości, łą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ń z rodzicem i rozmiarów, podczas gdy przejście po zbiorze mieszającym wymaga tylko jednego zbioru.
Podobne zadania
Zadania oparte na tych samych pomysłach. Rozwiązanie dwóch lub trzech utrwala schemat.
def longestConsecutive(nums):
# Napisz kod tutajTest #1
Test #2
Test #3
Argument
nums = [40, 4, 39, 1, 3, 2, 41]
Oczekiwany wynik
4