LeetCode-Meditationen: Fehlende Zahl

Beginnen wir mit der Beschreibung dieses Problems:

Gegeben sei ein Array mit n unterschiedlichen Zahlen im Bereich [0, n], gib die einzige Zahl im Bereich zurück, die im Array fehlt.

Zum Beispiel:

Input: nums = [3, 0, 1]
Output: 2

Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0, 3]. 2 is the missing number in the range since it does not appear in nums.

Oder:

Input: nums = [0, 1]
Output: 2

Explanation: n = 2 since there are 2 numbers, so all numbers are in the range [0, 2]. 2 is the missing number in the range since it does not appear in nums.

Oder:

Input: nums = [9, 6, 4, 2, 3, 5, 7, 0, 1]
Output: 8

Explanation: n = 9 since there are 9 numbers, so all numbers are in the range [0, 9]. 8 is the missing number in the range since it does not appear in nums.

Es wird auch angegeben, dass alle Zahlen von Zahlen einzigartig sind.

---

Eine einfache Möglichkeit, dieses Problem zu lösen, besteht darin, die Gesamtsumme des Bereichs zu ermitteln und dann die Summe des angegebenen Arrays zu subtrahieren. Übrig bleibt die fehlende Zahl.

Mit Reduzieren können Sie die Zahlen wie folgt summieren:

function missingNumber(nums: number[]): number {
  return Array.from({ 
    length: nums.length + 1 
  }, (_, idx) => idx).reduce((acc, item) => acc + item, 0) 
  - nums.reduce((acc, item) => acc + item, 0);
}

Zuerst erstellen wir ein Array mit Werten von 0 bis nums.length 1 und erhalten seine Summe, dann subtrahieren wir die Summe der nums davon.

Die zeitlichen und räumlichen Komplexitäten werden jedoch sein $O(n)$O(n) Mit dieser Lösung erstellen wir ein Array für den Bereich.

Mit der Bitmanipulation können wir eine (speichermäßig) effizientere Lösung finden.
Tatsächlich können wir eine XOR-Operation verwenden, um uns dabei zu helfen.

Zur Erinnerung: XOR ergibt 1, wenn beide Bits unterschiedlich sind – das heißt, eines davon ist 0 und das andere ist 1.
Wenn wir eine Zahl mit sich selbst XOR-verknüpfen, ergibt sich 0, da alle Bits gleich sind.

Zum Beispiel ist 3 im Binärformat 11, wenn wir 11 ^ 11 machen, ist das Ergebnis 0:

const n = 3;
const result = n ^ n; // 0

Mit anderen Worten: Eine XOR-Verknüpfung einer Zahl mit sich selbst führt zu 0.

Wenn wir mit jeder Zahl im Array mit den Indizes eine XOR-Verknüpfung durchführen, heben sich schließlich alle auf (Ergebnis 0) und es bleibt nur die fehlende Zahl übrig.

Sie könnten denken, dass nicht alle Zahlen ihren Index haben. Wenn Nums beispielsweise [3, 0, 1] ist, ist es offensichtlich, dass 3 nicht einmal einen „Index 3“ hat, der ihr zugeordnet werden kann!

Dazu können wir damit beginnen, unser Ergebnis auf nums.length zu initialisieren. Selbst wenn die fehlende Zahl nun gleich nums.length ist, behandeln wir diesen Grenzfall.

let result = nums.length;

Außerdem ist XOR kommutativ und assoziativ, daher ist es nicht wichtig, an welchem ​​Index eine Zahl erscheint (oder keinen hat, wie im Beispiel oben) – sie heben sich irgendwann auf.

Jetzt können wir mit einer for-Schleife das XOR mit dem bitweisen XOR-Zuweisungsoperator durchführen:

for (let i = 0; i < nums.length; i++) {
  result ^= i ^ nums[i];
}

Und das Endergebnis ist die fehlende Zahl. Die Lösung insgesamt sieht so aus:

Input: nums = [3, 0, 1]
Output: 2

Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0, 3]. 2 is the missing number in the range since it does not appear in nums.

Zeit- und Raumkomplexität

Die Zeitkomplexität ist wieder da $O(n)$O(n) Während wir jede Zahl im Array durchlaufen, wird der Platz jedoch komplexer $O(1)$O(1) da wir keinen zusätzlichen Speicherbedarf haben, der mit zunehmender Eingabegröße wächst.

---

Als nächstes werfen wir einen Blick auf das letzte Problem der gesamten Serie, die Summe zweier Ganzzahlen. Bis dahin viel Spaß beim Codieren.

Das obige ist der detaillierte Inhalt vonLeetCode-Meditationen: Fehlende Zahl. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!