Missing Number

Q: Wie hoch ist die Zeitkomplexität von „Missing Number“?

Die Lösungen mit Summe und XOR laufen beide in O(n) -Zeit mit O(1) zusätzlichem Speicherplatz, da sie jeden Wert einmal lesen und eine Zahl speichern. Die Liste für jeden Kandidaten zu durchsuchen, dauert O(n²) . Zuerst zu sortieren und dann nach der Lücke zu suchen, dauert O(n log n) .

Q: Kannst du „Missing Number“ mit einer Hash-Menge lösen?

Ja. Füge jeden Wert in eine Menge ein, prüfe dann 0 bis n und gib die erste Zahl zurück, die in der Menge fehlt. Das läuft in O(n) Zeit, benötigt aber zusätzlichen Speicherplatz von O(n) , den die Summen- und XOR-Methoden vermeiden.

LeichtBitmanipulation Mathe und Simulation

+10

Du erhältst eine Liste nums mit n verschiedenen Ganzzahlen, die jeweils zwischen 0 und n liegen. Der Bereich von 0 bis n umfasst n+1 Zahlen, daher fehlt genau eine davon in der Liste. Gib diese fehlende Zahl zurück.

Funktion

missingNumber(nums: integer-array) → integer

numsinteger-array: n verschiedene ganze Zahlen aus dem Bereich von 0 bis n, in beliebiger Reihenfolge
Gibt zurückinteger: die eine Zahl von 0 bis n, die nicht in nums enthalten ist

Einschränkungen

n == nums.length
1 ≤ n ≤ 10⁴
0 ≤ nums[i] ≤ n
Alle Werte in nums sind verschieden.

Beispiele

Eingabe: nums = [4, 2, 0, 1]
Ausgabe: 3
Erklärung: Die Liste hat 4 Werte, daher reicht der Bereich von 0 bis 4. Er enthält 0, 1, 2 und 4, und 3 ist die einzige Zahl ohne Übereinstimmung.

+13 versteckte Tests beim Einreichen

Weiterführende Frage

Wenn die Liste sortiert wäre, könntest du die fehlende Zahl mit einer binären Suche in O(log n) Zeit finden?

Tipps

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

0 von 3 geöffnet

Lösung

Du weißt genau, was die Liste enthalten sollte: jede ganze Zahl von 0 bis n. Jede dieser Zahlen einzeln zu suchen funktioniert, wiederholt aber für jede Zahl einen vollständigen Durchlauf. Stattdessen fasst du den gesamten Bereich und die Liste jeweils in einem einzigen zusammenfassenden Wert zusammen, der Summe oder dem XOR, und die Differenz zwischen beiden ist die fehlende Zahl. Das benötigt einen Durchlauf und keinen zusätzlichen Speicher.

Überprüfe jeden Kandidaten

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

Idee

Die Antwort ist eine der n+1 Zahlen von 0 bis n. Gehe sie der Reihe nach durch und durchsuche für jede die Liste. Der erste Kandidat, zu dem kein Wert passt, ist die fehlende Zahl.

Das ist korrekt, weil jede Zahl im Bereich entweder in der Liste steht oder die Antwort ist, und die Liste keine Duplikate enthält. Daher scheitert die Suche bei genau einem Kandidaten.

Das ist langsam, weil jeder Kandidat eine Durchsuchung von bis zu n Werten erfordert. Liegt die Lücke nahe am oberen Ende, wird fast jeder Kandidat gesucht: Bei n = 10^4 und einer Lücke nahe dem Ende sind das etwa 5 × 10^7 Vergleiche. Eine Verdopplung der Liste vervierfacht den Aufwand.

Algorithmus

Durchlaufe candidate von 0 bis einschließlich n.
Durchsuche nums nach einem Wert, der candidate entspricht.
Wenn die Suche den Wert findet, fahre mit dem nächsten Kandidaten fort.
Wenn die Suche ohne Treffer endet, gib candidate zurück.

def missingNumber(nums):
    n = len(nums)
    for candidate in range(n + 1):
        # "in" on a list scans it from the start: O(n) per candidate.
        if candidate not in nums:
            return candidate
    return -1

Ziehe die Summe von der erwarteten Summe ab

Idee

Wenn nichts fehlen würde, würde die Liste jede Zahl von 0 bis n enthalten, und ihre Summe wäre n(n+1)/2. Die tatsächliche Liste ist diese vollständige Menge, aus der eine Zahl entfernt wurde, daher ist ihre Summe genau um diese Zahl kleiner.

Für [4, 2, 0, 1] ist n gleich 4, und die Summe des vollständigen Bereichs ist 4 × 5 / 2 = 10. Die Summe der Liste ist 7, und 10 minus 7 ergibt 3.

Ein Durchlauf summiert die Liste, daher beträgt die Laufzeit O(n), und du behältst eine laufende Summe. Hier beträgt die vollständige Summe höchstens etwa 5 × 10^7, was in eine 32-Bit-Ganzzahl passt. Für viel größere Werte von n läuft die Formel bei einer 32-Bit-Ganzzahl über, daher führen die Java-, C-, C++-, C#- und Rust-Versionen die Berechnung mit 64 Bit durch.

Algorithmus

Sei n die Länge von nums.
Berechne die Gesamtsumme n(n+1)/2.
Addiere alle Werte in nums.
Gib die Gesamtsumme minus der Summe der Liste zurück.

def missingNumber(nums):
    n = len(nums)
    expected = n * (n + 1) // 2
    return expected - sum(nums)

XOR-verknüpfe die Indizes mit den Werten

Idee

XOR hebt Paare auf. a ^ a ist 0, a ^ 0 ist a, und die Reihenfolge der Operationen spielt keine Rolle. Wenn du also eine Menge von Zahlen XOR-verknüpfst, in der jede Zahl bis auf einen Wert zweimal vorkommt, heben sich die Paare auf und dieser Wert bleibt übrig.

Erzeuge eine solche Menge aus der Aufgabe: den Indizes 0 bis n sowie den Werten in nums. Eine Zahl, die in der Liste vorkommt, erscheint einmal als Index und einmal als Wert und hebt sich daher auf. Die fehlende Zahl erscheint nur als Index und bleibt deshalb übrig. Die Schleife durchläuft die Indizes 0 bis n-1. Beginne daher mit n, um den letzten Index einzubeziehen.

Für [4, 2, 0, 1]: Beginne mit 4 und verknüpfe dann 0 und 4, 1 und 2, 2 und 0 sowie 3 und 1 per XOR. Die 4er, 2er, 1er und 0er heben sich alle auf, und 3 bleibt übrig. Das ist ein Durchlauf mit einem einzigen laufenden Wert. Anders als die Summe wächst dieser nie über die bereits von n verwendeten Bits hinaus und kann daher nicht überlaufen.

Algorithmus

Setze result auf n, die Länge von nums.
Verknüpfe für jeden Index i result per XOR mit i und mit nums[i].
Gib result zurück.

def missingNumber(nums):
    # Start with n, the one index the loop below never reaches.
    result = len(nums)
    for i, value in enumerate(nums):
        result ^= i ^ value
    return result

Stolperfallen und Grenzfälle

Die meisten falschen Antworten entstehen an den beiden Enden des Bereichs.

Vergessen, dass n selbst fehlen kann. In [0, 1, 2] lautet die Antwort 3, was kein Index der Liste ist. Die XOR-Variante muss bei n beginnen, und ein sortierter Durchlauf, der nach dem ersten nums[i] != i sucht, muss n zurückgeben, wenn jede Position übereinstimmt.
Die falsche Bereichsgröße verwenden. Die Zahlen reichen von 0 bis n, das sind n+1 Zahlen, also ist die vollständige Summe n(n+1)/2, nicht (n-1)n/2.
Annehmen, dass 0 immer vorkommt. In [1] lautet die Antwort 0, und Code, der seine Suche bei 1 beginnt, übersieht diese Zahl.
Überlauf bei der Summenvariante. Bei 32-Bit-Arithmetik läuft das Produkt n(n+1) über, sobald n etwa 46.000 überschreitet, bevor die Division durch 2 helfen kann, und n(n+1)/2 selbst passt ab ungefähr 65.000 nicht mehr. Verwende 64-Bit-Arithmetik oder XOR.

Häufige Fragen4

Wie hoch ist die Zeitkomplexität von „Missing Number“?

Die Lösungen mit Summe und XOR laufen beide in O(n)-Zeit mit O(1) zusätzlichem Speicherplatz, da sie jeden Wert einmal lesen und eine Zahl speichern. Die Liste für jeden Kandidaten zu durchsuchen, dauert O(n²). Zuerst zu sortieren und dann nach der Lücke zu suchen, dauert O(n log n).

Warum findet XOR die fehlende Zahl?

Das XOR-Verknüpfen einer Zahl mit sich selbst ergibt 0, das XOR-Verknüpfen mit 0 ändert nichts, und die Reihenfolge spielt keine Rolle. Wenn du alle Indizes von 0 bis n zusammen mit allen Werten per XOR verknüpfst, kommt jede Zahl, die in der Liste steht, zweimal vor und hebt sich auf. Die fehlende Zahl kommt nur einmal vor, und zwar als Index, daher ist sie das Ergebnis.

Solltest du die Summenformel oder XOR verwenden?

Beide benötigen einen Durchlauf und konstanten Speicherplatz. Die Summe lässt sich leichter erklären, aber bei 32-Bit-Arithmetik läuft das Produkt n(n+1) über, sobald n etwa 46.000 überschreitet. Daher brauchst du 64-Bit-Arithmetik. Bei XOR gibt es keinen Überlauf. In Python, Ruby und anderen Sprachen mit Ganzzahlen ohne feste Obergrenze verschwindet der Unterschied.

Kannst du „Missing Number“ mit einer Hash-Menge lösen?

Ja. Füge jeden Wert in eine Menge ein, prüfe dann 0 bis n und gib die erste Zahl zurück, die in der Menge fehlt. Das läuft in O(n) Zeit, benötigt aber zusätzlichen Speicherplatz von O(n), den die Summen- und XOR-Methoden vermeiden.

Python

def missingNumber(nums):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

nums = [4, 2, 0, 1]

Erwartet

Missing Number

Funktion

Einschränkungen

Beispiele

Tipps

Lösung

Überprüfe jeden Kandidaten

Ziehe die Summe von der erwarteten Summe ab

XOR-verknüpfe die Indizes mit den Werten

Stolperfallen und Grenzfälle

Häufige Fragen4

Ähnliche Aufgaben