Longest Consecutive Sequence
Du erhältst ein Array von Ganzzahlen nums in keiner bestimmten Reihenfolge. Eine aufeinanderfolgende Sequenz ist eine Gruppe von Werten x, x+1, x+2 und so weiter, von denen jeder irgendwo in nums vorkommt. Gib die Länge der längsten aufeinanderfolgenden Sequenz zurück. Ein Wert, der mehr als einmal vorkommt, zählt nur einmal.
Funktion
- numsinteger-array
- die ganzen Zahlen, in beliebiger Reihenfolge; Wiederholungen sind erlaubt
- Gibt zurückinteger
- die Länge der längsten Folge aufeinanderfolgender Werte in nums
Einschränkungen
1 ≤ nums.length ≤ 104-109 ≤ nums[i] ≤ 109- Werte können sich wiederholen. Die Positionen im Array spielen keine Rolle, sondern nur, welche Werte vorhanden sind.
Beispiele
- Eingabe
- nums = [40, 4, 39, 1, 3, 2, 41]
- Ausgabe
- 4
- Erklärung
1,2,3und4sind alle vorhanden, eine Folge von 4, obwohl sie über das Array verstreut sind. Die andere Folge, von39bis41, umfasst nur 3 Werte.
- Eingabe
- nums = [7, 3, 7, 5, 6, 5]
- Ausgabe
- 3
- Erklärung
5,6und7bilden eine Folge von 3 Zahlen. Die zweite7und die zweite5tragen nichts bei, und3kann nicht dazugehören, weil4fehlt.
- Eingabe
- nums = [10, 30, 20]
- Ausgabe
- 1
- Erklärung
- Keine zwei Werte unterscheiden sich um 1, daher enthält jeder Lauf einen einzelnen Wert und die Antwort ist 1.
+17 versteckte Tests beim Einreichen
Weiterführende Frage
Angenommen, die Werte treffen nacheinander ein und nach jedem Wert musst du die längste zusammenhängende Folge bis dahin angeben. Kannst du die Antwort in durchschnittlich O(1) Zeit pro Wert aktuell halten?
Tipps
Öffne sie nacheinander. Jeder verrät ein bisschen mehr.
Probiere jeden Wert als erste Zahl einer Folge aus und zähle aufwärts. Welche Frage stellst du immer wieder, und wie viel kostet jede Antwort, wenn du im Array danach suchst?
Die Frage lautet: „Ist
x+1im Array?“ Ein Hash-Set beantwortet diese Frage durchschnittlich in konstanter Zeit und entfernt außerdem die Duplikate.Beginne nur bei einem Wert
xmit dem Zählen, dessen Vorgängerx-1in der Menge fehlt. Gehe von dort zux+1,x+2und so weiter, solange die Menge diese Werte enthält, und behalte den längsten Lauf bei. Jeder Wert wird dann nur von einem Lauf durchlaufen.
Lösung
Die Werte einer Folge können an beliebiger Stelle im Array stehen, daher kannst du die Folgen nicht von links nach rechts ablesen. Durch Sortieren werden sie in O(n log n) angeordnet. Ein Hash-Set ist effizienter: Es prüft in O(1), ob x+1 vorhanden ist, und wenn du nur bei Werten zählst, bei denen x-1 fehlt, wird jeder Wert nur einmal durchlaufen. Dadurch benötigt die gesamte Suche O(n).
Zähle von jedem Wert aus weiter, indem du das Array durchsuchst
Korrekt, wird aber bei den größten Tests nicht fertig
Idee
Betrachte jeden Wert als möglichen Anfang einer Folge. Suche im Array nach x+1, ausgehend von x; wenn er dort ist, suche nach x+2 und fahre fort, bis ein Wert fehlt. Die Anzahl der erreichten Werte ist die Folge, die bei x beginnt, und die größte dieser Längen ist die Antwort.
Das ist korrekt, weil jede Folge einen kleinsten Wert hat, dieser Wert in nums enthalten ist und die Schleife ihn als Anfang ausprobiert und die ganze Folge durchläuft. Wiederholungen schaden nicht: Sie probieren denselben Anfang lediglich zweimal aus.
Das Verfahren ist aus zwei Gründen langsam. Jede Prüfung, ob ein Wert vorhanden ist, liest bis zu n Werte, und eine lange Folge wird von jedem ihrer Elemente aus erneut durchlaufen. Nimm 10^4 Werte, die eine einzige gemischte Folge bilden: Die Durchläufe summieren sich auf etwa n²/2 = 5 × 10^7 Schritte, und jeder Schritt durchsucht im Durchschnitt die Hälfte des Arrays. Das sind ungefähr 2.5 × 10^11 Vergleiche.
Algorithmus
- Setze
bestauf 0. - Setze für jeden Wert
startinnumscurrentaufstartundlengthauf 1. - Solange ein Durchlauf von
numscurrent+1findet, erhöhecurrentundlengthum 1. - Speichere
lengthinbest, wenn es größer ist. - Gib
bestzurück.
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 bestSortieren, dann Folgen zählen
Idee
Beim Sortieren werden die Werte jedes Laufs nebeneinander angeordnet. [40, 4, 39, 1, 3, 2, 41] wird zu [1, 2, 3, 4, 39, 40, 41], und die Läufe lassen sich von links nach rechts ablesen: von 1 bis 4, dann ein Sprung zu 39.
Gehe die sortierten Werte durch und behalte die Länge des aktuellen Laufs im Blick. Ein Wert, der um eins größer als der vorherige ist, verlängert ihn. Ein Wert, der dem vorherigen entspricht, ist eine Wiederholung: Überspringe ihn, da er den Lauf weder verlängert noch beendet. Jeder andere Wert ist eine Lücke, und dort beginnt ein neuer Lauf der Länge 1.
Das Sortieren kostet O(n log n) und das Durchlaufen O(n). Sortieren an Ort und Stelle benötigt kein zusätzliches Array, ordnet aber die Eingabe des Aufrufers neu; Sprachen, die eine Kopie sortieren, verwenden O(n) Speicher.
Algorithmus
- Sortiere
numsaufsteigend. - Setze
bestundrunauf 1, da das Array niemals leer ist. - Überspringe für jeden Index
iab 1nums[i], wenn es gleichnums[i-1]ist. - Wenn
nums[i]gleichnums[i-1]+1ist, addiere 1 zurun; andernfalls setzerunauf 1. Speichereruninbest, wenn es größer ist. - Gib
bestzurück.
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 bestHash-Set, wobei nur ab dem Start jedes Durchlaufs gezählt wird
Idee
Füge jeden Wert in eine Hash-Menge ein. Die Frage „Ist x+1 vorhanden?“ kostet dann im Durchschnitt O(1) statt eines Durchlaufs, und Duplikate werden zu einem einzigen Eintrag zusammengefasst.
Von jedem Wert aus loszulaufen, würde weiterhin Arbeit wiederholen: In der Folge 1, 2, 3, 4 würdest Du von 1 aus 3 Schritte machen, von 2 aus 2 und von 3 aus 1. Beginne einen Durchlauf also nur beim ersten Wert einer Folge. Ein Wert x ist genau dann der erste, wenn x-1 nicht in der Menge enthalten ist. In [40, 4, 39, 1, 3, 2, 41] kommen nur 1 und 39 infrage: Von 1 aus erreichst Du 4, also eine Länge von 4, und von 39 aus erreichst Du 41, also eine Länge von 3.
Jeder Wert gehört genau einer Folge an, und nur der Durchlauf vom ersten Wert dieser Folge führt über ihn, sodass alle Durchläufe zusammen höchstens n Schritte benötigen. Mit einer Prüfung auf Zugehörigkeit pro Wert und dem Erstellen der Menge beträgt die Gesamtzeit O(n), und der Speicherbedarf für die Menge ist O(n).
Durchlaufe die Menge, nicht nums. Wenn der erste Wert einer Folge mit 2.500 Werten in nums 2.000-mal vorkommt, durchläuft eine Schleife über nums diese Folge 2.000-mal.
Algorithmus
- Füge jeden Wert aus
numsin eine Hash-Mengevaluesein und setzebestauf 0. - Überspringe für jeden Wert
xin der Menge den Wert, wennx-1in der Menge ist: Er ist nicht der erste Wert seiner Folge. - Setze andernfalls
endaufxund erhöhe es um 1, solangeend+1in der Menge ist. - Speichere
end-x+1inbest, wenn der Wert größer ist. - Gib
bestzurück.
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
Stolperfallen und Grenzfälle
Die meisten falschen Antworten entstehen durch doppelte Werte und die meisten langsamen Antworten dadurch, dass derselbe zusammenhängende Abschnitt mehr als einmal durchlaufen wird.
- Eine Wiederholung als Lücke oder als Schritt nach dem Sortieren behandeln. In
[1, 2, 2, 3]ergibt das Zurücksetzen des Abschnitts bei der zweiten2den Wert 2; zählt man sie als Schritt, ergibt sich 4. Die Antwort ist 3. bestbeim sortierten Durchlauf auf 0 setzen und nur innerhalb der Schleife aktualisieren. Ein Array mit einem Wert gibt dann 0 statt 1 zurück.- Bei jedem Wert der Menge beginnen, statt nur bei den Abschnittsanfängen. Die Antwort ist zwar richtig, aber ein Abschnitt mit
10^4Werten kostet5 × 10^7Schritte – genau die quadratische Arbeit, die durch die Menge vermieden werden sollte. - Über
numsstatt über die Menge iterieren, wenn sich Werte wiederholen. Der Abschnitt, der bei einem tausendfach vorkommenden Wert beginnt, wird tausendfach durchlaufen. - Werte in einem nach Werten indizierten Array markieren. Die Werte reichen bis
±10^9, daher müsste das Array2 × 10^9Einträge enthalten.
Häufige Fragen4
Wie hoch ist die Zeitkomplexität der längsten aufeinanderfolgenden Sequenz?
Die Lösung mit einer Hash-Menge benötigt im Durchschnitt O(n) Zeit und zusätzlichen Speicherplatz von O(n). Sortieren und anschließendes Zählen der Folgen benötigt O(n log n) Zeit. Die Suche im Array nach jedem nächsten Wert ohne eine Menge benötigt bis zu O(n³).
Warum ist die Lösung mit einem Hash-Set O(n), obwohl sie eine while-Schleife innerhalb einer for-Schleife enthält?
Die innere Schleife wird nur für einen Wert ausgeführt, dessen linker Nachbar x-1 fehlt, also für den ersten Wert seiner Folge. Jeder Wert wird von der Durchlaufbewegung seiner eigenen Folge und von keiner anderen Durchlaufbewegung übersprungen, sodass alle inneren Schleifen zusammen höchstens n Schritte benötigen. Die äußere Schleife fügt pro Wert eine Prüfung hinzu, insgesamt also O(n).
Kannst du die längste aufeinanderfolgende Folge ohne zusätzlichen Speicher lösen?
Ja, wenn du die Eingabe umordnen darfst: Sortiere sie direkt und zähle die Folgen in einem Durchlauf, wobei du Wiederholungen überspringst. Das benötigt zusätzlichen Speicherplatz von O(1), aber eine Laufzeit von O(n log n). Für die Lösung mit O(n) wird die Hash-Menge benötigt.
Kann Union-Find die längste aufeinanderfolgende Sequenz lösen?
Ja. Erstelle für jeden unterschiedlichen Wert eine Menge, verbinde x mit x+1, wenn beide vorhanden sind, und gib die Größe der größten Menge zurück. Das läuft in annähernd O(n) Zeit, benötigt aber eine Zuordnung von Werten zu Indizes, Elternverweise und Größen, während der Durchlauf mit der Hashtabelle dieselbe Aufgabe mit einer Menge und zwei Schleifen erledigt.
Ähnliche Aufgaben
Aufgaben mit denselben Ideen. Wer zwei oder drei davon löst, behält das Muster.
Python
def longestConsecutive(nums):
# Schreibe hier den CodeFall 1
Fall 2
Fall 3
Eingabe
nums = [40, 4, 39, 1, 3, 2, 41]
Erwartet
4