Longest Consecutive Sequence

Q: 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 O(n) zusätzlichen Speicher. Das Sortieren und Zählen der Folgen benötigt O(n log n) . Die Suche im Array nach jedem nächsten Wert ohne eine Menge benötigt bis zu O(n³) .

MittelHashing

+10

Du erhältst ein Array von Ganzzahlen nums in keiner bestimmten Reihenfolge. Eine Folge aufeinanderfolgender Zahlen 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 Folge aufeinanderfolgender Zahlen zurück. Ein Wert, der mehr als einmal vorkommt, wird nur einmal gezählt.

Funktion

longestConsecutive(nums: integer-array) → integer

numsinteger-array: die ganzen Zahlen, in beliebiger Reihenfolge, Wiederholungen sind erlaubt
Gibt zurückinteger: die Länge der längsten Folge aufeinanderfolgender Werte, die in nums vorkommt

Einschränkungen

1 ≤ nums.length ≤ 10⁴
-10⁹ ≤ nums[i] ≤ 10⁹
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, 3 und 4 sind alle vorhanden, eine Folge von 4, obwohl sie über das Array verteilt sind. Die andere Folge, von 39 bis 41, hat nur 3 Werte.

Eingabe: nums = [7, 3, 7, 5, 6, 5]
Ausgabe: 3
Erklärung: 5, 6 und 7 bilden eine Folge von 3. Die zweite 7 und die zweite 5 tragen nichts bei, und 3 kann nicht dazukommen, weil 4 fehlt.

Weiterführende Frage

Angenommen, Werte treffen einzeln ein und nach jedem musst du die längste bisherige Folge melden. Kannst du die Antwort im Durchschnitt in O(1)-Zeit pro Wert aktuell halten?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Die Werte einer Folge können sich an beliebigen Stellen im Array befinden. Durch Sortieren werden sie in O(n log n) angeordnet. Ein Hash-Set beantwortet „Ist x+1 hier?“ in O(1), und wenn du nur bei Werten zählst, bei denen x-1 fehlt, wird jeder Wert genau einmal durchlaufen: insgesamt O(n).

Von jedem Wert aus hochzählen, indem du das Array durchsuchst

Korrekt, wird aber bei den größten Tests nicht fertig

Idee

Betrachte jeden Wert als möglichen Start einer Folge. Suche im Array nach x+1 ausgehend von x, dann nach x+2, bis ein Wert fehlt, und behalte die längste gezählte Folge. Jede Folge hat einen kleinsten Wert in nums, und die Schleife durchläuft von dort aus die ganze Folge.

Bei jeder Suche werden bis zu n Werte gelesen, und eine lange Folge wird von jedem ihrer Elemente aus erneut durchlaufen. Bei 10^4 Werten, die eine einzige durchmischte Folge bilden, benötigen die Durchläufe etwa n²/2 = 5 × 10^7 Schritte, wobei jeder im Durchschnitt die Hälfte des Arrays durchsucht: etwa 2.5 × 10^11 Vergleiche.

Algorithmus

Setze best auf 0.
Setze für jeden Wert start in nums current auf start und length auf 1.
Wenn ein Durchlauf von nums current+1 findet, addiere 1 zu current und zu length.
Speichere length in best, wenn es größer ist.
Gib best zurü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 best

Sortieren, dann Folgen zählen

Idee

Durch das Sortieren stehen die Werte jedes Laufs nebeneinander: [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.

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. Eine Wiederholung verlängert den Lauf nicht und beendet ihn auch nicht, also überspringe sie. Jeder andere Wert beginnt einen neuen Lauf der Länge 1.

Das Sortieren kostet O(n log n) und das Durchgehen O(n). Sortieren an Ort und Stelle benötigt kein zusätzliches Array; Sprachen, die eine Kopie sortieren, verwenden O(n) Speicher.

Algorithmus

Sortiere nums aufsteigend.
Setze best und run auf 1, da das Array nie leer ist.
Überspringe für jeden Index i ab 1 nums[i], wenn es gleich nums[i-1] ist.
Wenn nums[i] gleich nums[i-1]+1 ist, erhöhe run um 1; andernfalls setze run auf 1. Speichere run in best, wenn es größer ist.
Gib best zurü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 best

Hash-Set, wobei nur vom Anfang jedes Durchlaufs an gezählt wird

Idee

Bei jedem Wert in einer Hash-Menge kostet eine Zugehörigkeitsprüfung durchschnittlich O(1), und Duplikate werden zu einem Eintrag zusammengefasst.

Von jedem Wert aus loszugehen, würde weiterhin Arbeit wiederholen: Im Lauf 1, 2, 3, 4 würdest Du von 1 aus 3 Schritte machen, von 2 aus 2 und von 3 aus 1. Gehe daher nur vom ersten Wert eines Laufs aus. Das ist genau ein Wert x, für den x-1 fehlt. In Beispiel 1 kommen nur 1 und 39 infrage; sie ergeben Läufe der Länge 4 und 3.

Jeder Wert gehört zu genau einem Lauf und wird nur beim Durchlaufen dieses Laufs berücksichtigt, daher umfassen alle Durchläufe zusammen höchstens n Schritte. Mit einer Prüfung pro Wert beträgt die Gesamtlaufzeit O(n), und die Menge benötigt O(n) Speicherplatz.

Algorithmus

Füge jeden Wert von nums in eine Hash-Menge values ein und setze best auf 0.
Überspringe für jeden Wert x in der Menge den Wert, wenn x-1 in der Menge ist: Er ist nicht der erste Wert seiner Folge.
Setze andernfalls end auf x und erhöhe es um 1, solange end+1 in der Menge ist.
Speichere end-x+1 in best, wenn der Wert größer ist.
Gib best zurü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

Eine Wiederholung nach dem Sortieren als Lücke oder als Schritt behandeln. In [1, 2, 2, 3] ergibt das Zurücksetzen der Folge bei der zweiten 2 den Wert 2, und sie als Schritt zu zählen, ergibt 4. Die Antwort ist 3.
best beim Durchlaufen der sortierten Wertefolge auf 0 setzen und nur innerhalb der Schleife aktualisieren. Bei einem Array mit einem Wert wird dann 0 statt 1 zurückgegeben.
Bei jedem Wert der Menge beginnen, statt nur bei den Anfängen von Folgen. Eine Folge mit 10^4 Werten erfordert dann 5 × 10^7 Schritte.
Über nums statt über die Menge iterieren. Wenn der erste Wert einer Folge der Länge 2.500 2.000-mal vorkommt, wird die Folge 2.000-mal durchlaufen.
Ein Array anhand des Werts indizieren. Die Werte reichen bis ±10^9, daher benötigt es 2 × 10^9 Einträge.

Häufige Fragen3

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 O(n) zusätzlichen Speicher. Das Sortieren und Zählen der Folgen benötigt O(n log n). Die Suche im Array nach jedem nächsten Wert ohne eine Menge benötigt bis zu O(n³).

Kannst du die längste aufeinanderfolgende Sequenz 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). Die Lösung mit O(n) benötigt das Hash-Set.

Kann Union-Find die längste aufeinanderfolgende Folge lösen?

Ja. Mach aus jedem unterschiedlichen Wert eine Menge, verbinde x mit x+1, wann immer 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, Elternverknüpfungen und Größen, während der Hash-Set-Durchlauf nur ein Set benötigt.

def longestConsecutive(nums):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argument

nums = [40, 4, 39, 1, 3, 2, 41]

Erwartete Ausgabe

Longest Consecutive Sequence

Funktion

Einschränkungen

Beispiele

Tipps

Lösung

Von jedem Wert aus hochzählen, indem du das Array durchsuchst

Sortieren, dann Folgen zählen

Hash-Set, wobei nur vom Anfang jedes Durchlaufs an gezählt wird

Stolperfallen und Grenzfälle

Häufige Fragen3

Ähnliche Aufgaben