Single Number
Du erhältst eine Liste nums, in der jeder Wert genau zweimal vorkommt, außer einem Wert, der nur einmal vorkommt. Gib den Wert zurück, der einmal vorkommt.
Funktion
- numsinteger-array
- eine Liste, in der jeder Wert zweimal vorkommt, bis auf einen
- Gibt zurückinteger
- der Wert, der nur einmal vorkommt
Einschränkungen
1 ≤ nums.length < 104-104 ≤ nums[i] ≤ 104- Jeder Wert kommt genau zweimal vor, mit Ausnahme eines Werts, der genau einmal vorkommt.
Beispiele
- Eingabe
- nums = [8, 3, 8]
- Ausgabe
- 3
- Erklärung
- 8 erscheint zweimal und 3 erscheint einmal, also lautet die Antwort 3.
- Eingabe
- nums = [5, -2, 7, 5, 7]
- Ausgabe
- -2
- Erklärung
- 5 und 7 kommen jeweils zweimal vor, und -2 ist der einzige Wert, der einmal vorkommt. Eine negative Antwort findet man auf dieselbe Weise wie eine positive.
- Eingabe
- nums = [42]
- Ausgabe
- 42
- Erklärung
- Eine Liste mit einem Wert hat überhaupt keine Paare, also ist dieser Wert die Antwort.
+13 versteckte Tests beim Einreichen
Weiterführende Frage
Was wäre, wenn jeder Wert dreimal vorkäme, bis auf einen? XOR allein hebt die Dreiergruppen nicht mehr auf. Kannst du den einzelnen Wert trotzdem in O(n)-Zeit und mit O(1) zusätzlichem Speicher finden?
Tipps
Öffne sie nacheinander. Jeder verrät ein bisschen mehr.
Wenn jedes Paar gleicher Werte verschwinden könnte, bliebe nur die Antwort übrig. Gibt es eine Operation, die zwei gleiche Zahlen in nichts verwandelt?
XOR bewirkt:
x ^ xist0undx ^ 0istx. Es ist außerdem reihenfolgeunabhängig, sodass die beiden Kopien eines Werts nicht nebeneinander stehen müssen, um sich aufzuheben.Behalte eine Variable, die bei
0beginnt. Verknüpfe jeden Wert vonnumsper XOR damit und gib sie anschließend zurück. Eine Map und Sortieren sind nicht erforderlich.
Lösung
Den einen Wert ohne Partner zu finden, ist ein Zählproblem, und eine Hash-Map zählt in einem Durchlauf jeden Wert. Der Haken ist der Speicherbedarf: Eine Map wächst mit der Liste. XOR macht das Zählen ganz überflüssig, denn XOR mit sich selbst ergibt 0. Verknüpfe die gesamte Liste mit XOR, und jedes Paar hebt sich selbst auf. So bleibt der einzelne Wert in einem Durchlauf mit nur einer Variablen übrig.
Jeden Wert durch Abzählen ermitteln
Korrekt, wird aber bei den größten Tests nicht fertig
Idee
Nimm jeden Wert der Reihe nach und durchsuche die gesamte Liste, um zu zählen, wie oft er vorkommt. Ein Wert aus einem Paar zählt 2. Der einzelne Wert zählt 1, also gib den ersten Wert zurück, dessen Anzahl 1 beträgt.
Das ist korrekt, weil sich die Anzahlen direkt aus der Definition der Antwort ergeben und außer einem Zähler kein zusätzlicher Speicher benötigt wird.
Das ist langsam, weil jeder der n Werte eine vollständige Durchsuchung von n Werten auslöst. Wenn der einzelne Wert am Ende einer Liste mit 9.999 Elementen steht, sind das fast 10^8 Vergleiche.
Algorithmus
- Gehe jeden Wert in
numsdurch. - Durchsuche die gesamte Liste und zähle die Werte, die damit übereinstimmen.
- Wenn die Anzahl 1 ist, gib diesen Wert zurück.
def singleNumber(nums):
for value in nums:
# count() scans the whole list: O(n) per value.
if nums.count(value) == 1:
return value
return 0Mit einer Hashmap zählen
Idee
Die Liste für jeden Wert erneut zu durchsuchen, wiederholt Arbeit. Zähle stattdessen alle Werte in einem Durchlauf: mit einer Hashtabelle von Werten zu Häufigkeiten, wobei jeder Schritt die Häufigkeit des aktuellen Werts um 1 erhöht.
Für [5, -2, 7, 5, 7] enthält die Tabelle am Ende 5 → 2, -2 → 1, 7 → 2. Ein zweiter Durchlauf über die Tabelle findet den Eintrag mit der Häufigkeit 1, also -2.
Jeder Wert erfordert eine Aktualisierung der Tabelle, daher beträgt die Laufzeit O(n). Die Tabelle enthält etwa n/2 Einträge, was O(n) zusätzlichen Speicherplatz bedeutet. In C, das keine eingebaute Tabelle hat, erfüllt ein Array mit Zählern, indiziert durch value + 10^4, denselben Zweck, da die Werte klein sind.
Algorithmus
- Erstelle eine leere Map, die Werte ihren Häufigkeiten zuordnet.
- Erhöhe für jeden Wert in
numsseine Häufigkeit um 1. - Gehe die Map durch und gib den Wert zurück, dessen Häufigkeit 1 ist.
def singleNumber(nums):
counts = {}
for value in nums:
counts[value] = counts.get(value, 0) + 1
for value, count in counts.items():
if count == 1:
return value
return 0XOR alle Werte
Idee
XOR vergleicht zwei Zahlen Bit für Bit und setzt ein Bit, wenn sie sich unterscheiden. Daraus folgen drei Tatsachen: x ^ x = 0, x ^ 0 = x, und die Reihenfolge der Operationen spielt keine Rolle.
Verknüpfe also die ganze Liste per XOR in einer Variablen, die mit 0 beginnt. Du kannst die Operationen so umgruppieren, dass jedes Paar auf sein Gegenstück trifft und jedes Paar zu 0 wird. Übrig bleibt 0 ^ single, also der einzelne Wert. Für [8, 3, 8]: 0 ^ 8 = 8, dann 8 ^ 3 = 11, dann 11 ^ 8 = 3.
Auch negative Zahlen funktionieren. XOR arbeitet mit den Bits der Zweierkomplementdarstellung, und zwei gleiche negative Zahlen haben gleiche Bits, sodass sie sich wie jedes andere Paar aufheben. Die Schleife liest jeden Wert einmal und behält eine Variable: O(n) Zeit und O(1) zusätzlichen Speicher.
Algorithmus
- Setze
resultauf 0. - Setze für jeden Wert in
numsresultaufresult ^ value. - Gib
resultzurück.
def singleNumber(nums):
result = 0
for value in nums:
result ^= value
return result
Stolperfallen und Grenzfälle
Die XOR-Schleife ist kurz, daher verstecken sich die Fehler darin, wo sie beginnt und auf welche Alternativen man zurückgreift.
resultmitnums[0]beginnen und dann über jeden Wert iterieren, einschließlich Index 0. Der erste Wert wird zweimal per XOR verknüpft und hebt sich selbst auf. Beginne bei 0 oder überspringe Index 0.- Sortieren und Nachbarn in Zweierschritten vergleichen und dann vergessen, dass der einzelne Wert das letzte Element sein kann. In
[1, 1, 2]gibt es kein Paar mit unterschiedlichen Werten, und die Antwort ist die übrig gebliebene 2. 2 × sum(distinct values) - sum(nums)verwenden. Das liefert zwar die richtige Zahl, aber die Menge der unterschiedlichen Werte benötigtO(n)Speicher, den die XOR-Version einspart.- Erwarten, dass XOR auch bei anderen Häufigkeiten funktioniert. Es hebt Werte auf, die eine gerade Anzahl von Malen vorkommen. Käme ein Wert dreimal vor, bliebe eine Kopie übrig und würde die Antwort verfälschen.
Häufige Fragen4
Wie hoch ist die Zeitkomplexität von Single Number?
Die XOR-Lösung benötigt O(n) Zeit und O(1) zusätzlichen Speicherplatz, weil sie jeden Wert einmal liest und eine Variable verwendet. Eine Hash-Map benötigt ebenfalls O(n) Zeit, aber O(n) Speicher. Das Zählen jedes Werts mit einem neuen Durchlauf benötigt O(n²).
Warum löst XOR das Problem mit einer einzelnen Zahl?
Eine Zahl mit sich selbst zu XOR-verknüpfen ergibt 0, eine XOR-Verknüpfung mit 0 ändert nichts, und die Reihenfolge der Operationen spielt keine Rolle. Wenn du also die gesamte Liste mit XOR verknüpfst, kann jedes Paar zusammengefasst werden und hebt sich zu 0 auf. Nur der Wert ohne Partner bleibt übrig.
Funktioniert der XOR-Trick mit negativen Zahlen?
Ja. XOR arbeitet mit den Bits, in denen die Zahl gespeichert ist, und negative Zahlen werden im Zweierkomplement gespeichert. Zwei gleiche negative Zahlen haben identische Bits und heben sich daher genauso wie positive Zahlen genau auf. In [5, -2, 7, 5, 7] ist das Ergebnis -2.
Wie löst du es, wenn die anderen Werte dreimal vorkommen?
XOR hebt Paare auf, nicht Dreiergruppen, daher scheitert es in diesem Fall. Zähle stattdessen, bei wie vielen Werten jedes der 32 Bits gesetzt ist. Für jedes Bit ist dieser Zähler modulo 3 das entsprechende Bit des einzelnen Werts, da die Dreiergruppen Vielfache von 3 addieren. Das läuft weiterhin in O(n) Zeit mit O(1) zusätzlichem Speicher.
Ähnliche Aufgaben
Aufgaben mit denselben Ideen. Wer zwei oder drei davon löst, behält das Muster.
Python
def singleNumber(nums):
# Schreibe hier den CodeFall 1
Fall 2
Fall 3
Eingabe
nums = [8, 3, 8]
Erwartet
3