First Missing Positive

+10

Du erhältst ein unsortiertes Array aus Ganzzahlen nums. Gib die kleinste positive ganze Zahl (1 oder größer) zurück, die nicht in nums vorkommt. Das Array kann negative Zahlen, Nullen, wiederholte Werte und Werte enthalten, die viel größer als seine Länge sind.

Funktion

firstMissingPositive(nums: integer-array) → integer

numsinteger-array: die unsortierten Ganzzahlen, die sich wiederholen können und negativ, null oder sehr groß sein können
Gibt zurückinteger: die kleinste positive ganze Zahl, die in nums fehlt

Einschränkungen

1 ≤ nums.length ≤ 10⁴
-10⁹ ≤ nums[i] ≤ 10⁹
Die Werte sind in keiner bestimmten Reihenfolge angeordnet und können sich wiederholen.

Beispiele

Eingabe: nums = [5, -2, 1, 3, 2, 9]
Ausgabe: 4
Erklärung: 1, 2 und 3 sind alle im Array, und 4 ist es nicht, also lautet die Antwort 4. Die 5 und die 9 spielen keine Rolle, sobald ein kleinerer Wert fehlt.

Weiterführende Frage

Kannst du die Antwort in O(n) Zeit finden und dabei nur O(1) zusätzlichen Speicher verwenden?

Tipps

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

0 von 3 geöffnet

Lösung

Sortieren benötigt O(n log n) Zeit und ein Hash-Set O(n) zusätzlichen Speicher. Eine Schranke ist beiden überlegen: n Werte decken höchstens n der Zahlen von 1 bis n+1 ab, daher ist die Antwort höchstens n+1. Nur die Werte 1 bis n sind relevant, und das Array hat n Plätze, um sie zu erfassen, sodass der zusätzliche Speicher auf O(1) sinkt.

Probiere jeden Kandidaten mit einer vollständigen Suche aus

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

Idee

Teste die Kandidaten 1, 2, 3, ... der Reihe nach. Durchsuche für jeden Kandidaten das gesamte Array und gib den ersten Kandidaten zurück, den die Suche nicht findet. Aufgrund der Schranke testest du nie über n+1 hinaus.

Wenn das Array die Werte 1 bis n enthält, wird jeder Kandidat im Durchschnitt etwa auf halbem Weg gefunden. Für n = 10^4 sind das also etwa n²/2 = 5 × 10^7 Vergleiche.

Algorithmus

Setze candidate auf 1.
Durchsuche nums nach einem Element, das gleich candidate ist, und stoppe beim ersten Treffer.
Wenn kein Element übereinstimmt, gib candidate zurück.
Andernfalls addiere 1 zu candidate und durchsuche erneut. Du gehst niemals über n+1 hinaus.

def firstMissingPositive(nums):
    n = len(nums)
    # n values cannot cover all of 1..n+1, so one of these candidates is missing
    for candidate in range(1, n + 2):
        found = False
        for num in nums:
            if num == candidate:
                found = True
                break
        if not found:
            return candidate

Markiere die Werte 1 bis n in einem Flag-Array

Idee

Da die Antwort höchstens n+1 beträgt, überspringe alle Werte unter 1 oder über n. Ein boolesches Array present der Länge n+1 speichert die übrigen Werte, sodass ein Wert wie 10^9 niemals gespeichert wird. Gib das erste v von 1 bis n zurück, dessen Flag false ist, oder n+1, wenn alle Flags gesetzt sind.

Im ersten Beispiel gilt n = 6: Die Flags für 1, 2, 3 und 5 werden gesetzt, -2 und 9 werden übersprungen, und das erste nicht gesetzte Flag ist 4. Zwei lineare Durchläufe benötigen O(n) Zeit, und die Flags belegen O(n) Speicher.

Algorithmus

Erstelle present mit n+1 Flags, die auf false gesetzt sind.
Setze für jeden Wert v in nums mit 1 ≤ v ≤ n present[v] auf true.
Gib den ersten Wert v von 1 bis n zurück, dessen Flag false ist.
Gibt es keinen solchen Wert, gib n+1 zurück.

def firstMissingPositive(nums):
    n = len(nums)
    # present[v] says whether v is in nums; only 1..n can matter
    present = [False] * (n + 1)
    for num in nums:
        if 1 <= num <= n:
            present[num] = True
    for v in range(1, n + 1):
        if not present[v]:
            return v
    return n + 1

Platziere jeden Wert in einem eigenen Slot

Idee

Der Wert v gehört an den Index v-1. Wenn jeder Wert von 1 bis n an seinem Platz ist, gibt der erste Index i, an dem nicht i+1 steht, die Antwort an.

Tausche an jedem Index den Wert an seinen Platz, solange er zwischen 1 und n liegt und an seinem Platz nicht bereits dieser Wert steht. Der Wert, der zurückkommt, muss möglicherweise ebenfalls verschoben werden. Die Prüfung des Zielplatzes statt von i verhindert Endlosschleifen bei Duplikaten: In [1, 1] sieht die zweite 1 am Index 0 eine 1 und bleibt stehen.

Im ersten Beispiel schickt Index 0 die 5 an ihren Platz und danach die zurückkommende 2; später kommen die 1 und die 3 an ihren Platz. Übrig bleibt [1, 2, 3, -2, 5, 9]: Index 3 ist der erste falsche Platz, also lautet die Antwort 4.

Jeder Tausch bringt einen Wert endgültig an seinen Platz, daher führen die inneren Schleifen insgesamt höchstens n Tausche aus: O(n) Laufzeit und O(1) Speicher, außer in R, wo der veränderte Vektor kopiert wird.

Algorithmus

Für jeden Index i von 0 bis n-1:
Solange 1 ≤ nums[i] ≤ n und nums[nums[i]-1] ≠ nums[i] gilt, vertausche nums[i] mit nums[nums[i]-1].
Suche nach dem Platzierungsdurchlauf den ersten Index i, für den nums[i] ≠ i+1 gilt, und gib i+1 zurück.
Wenn jeder Platz seinen eigenen Wert enthält, gib n+1 zurück.

def firstMissingPositive(nums):
    n = len(nums)
    for i in range(n):
        # Keep swapping until slot i holds a value that has no slot or is already home
        while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
            home = nums[i] - 1
            nums[i], nums[home] = nums[home], nums[i]
    # The first slot that does not hold its own value names the answer
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1
    return n + 1

Stolperfallen und Grenzfälle

Die Vertauschungen beenden, wenn nums[i] == i+1, statt wenn der Zielplatz bereits den Wert enthält. Bei [1, 1] werden die beiden Einsen endlos vertauscht.
Mit if statt mit while vertauschen. Im ersten Beispiel erreicht die 2, die von Index 4 zurückkommt, nie Index 1, und du gibst 2 statt 4 zurück.
nums[i] = nums[nums[i]-1] schreiben und dann erneut mit nums[i] indizieren, wodurch der Zielindex nach seiner Änderung ausgelesen wird. Speichere zuerst den Zielindex.
Die Bereichsprüfung überspringen, wodurch 0, -2 oder 10^9 auf einen Index außerhalb des Arrays verweisen.
n zurückgeben, wenn jeder Platz richtig belegt ist. Für [4, 2, 1, 3] lautet die Antwort 5.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität von First Missing Positive?

Die Platzierungslösung benötigt O(n) Zeit und O(1) zusätzlichen Speicherplatz. Die while-Schleife befindet sich innerhalb einer for-Schleife, aber jeder Tausch platziert einen Wert an seinem endgültigen Index, sodass der gesamte Durchlauf höchstens n Tauschvorgänge ausführt. Die Version mit einem Flag-Array benötigt O(n) Zeit und O(n) Speicherplatz, und das Durchsuchen nach jedem Kandidaten benötigt O(n²).

Warum ist die Antwort nie größer als n+1?

Die Zahlen 1 bis n+1 sind n+1 verschiedene Werte, und ein Array der Länge n enthält höchstens n verschiedene Werte, also fehlt einer davon. Die Antwort ist genau dann n+1, wenn das Array jeden Wert von 1 bis n enthält.

Ändert die In-Place-Lösung das Eingabearray?

Ja, es ordnet die Werte neu an. Wenn der Aufrufer die ursprüngliche Reihenfolge benötigt, kopiere zuerst das Array. Dadurch steigt der zusätzliche Speicherbedarf wieder auf O(n). Eine andere In-place-Methode ersetzt jeden Wert außerhalb von 1 bis n durch n+1 und markiert dann, dass v vorhanden ist, indem sie nums[v-1] negativ macht; auch sie verändert das Array.

def firstMissingPositive(nums):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argument

nums = [5, -2, 1, 3, 2, 9]

Erwartete Ausgabe

First Missing Positive

Funktion

Einschränkungen

Beispiele

Tipps

Lösung

Probiere jeden Kandidaten mit einer vollständigen Suche aus

Markiere die Werte 1 bis n in einem Flag-Array

Platziere jeden Wert in einem eigenen Slot

Stolperfallen und Grenzfälle

Häufige Fragen3

Ähnliche Aufgaben