Intelligente Verwendung von XOR-Operator, um eine fehlende Nummer zu finden

Question

Ich bin auf dem folgenden Problem auf dem SeetCode gestoßen und versucht, es mit dem folgenden Code zu lösen, es scheint jedoch eine noch bessere Lösung zu sein, die Xor nutzt.LeetCODE hat eine Beschreibung für die XOR-Lösung, aber ich kann es jedoch nicht in seiner Gesamtheit erfassen.

Ich kann meinen Kopf einfach nicht umwickeln, warum wir fehlende Variable mit einer Anordnung lang initialisieren müssen, warum nicht mit null initialisieren, und wenn wir es mit null initialisieren, warum nichtDieses Algo finde die fehlende Nummer?Kann jemand es bitte erklären?

Folgendes war meine Lösung, bevor ich gelernt habe, dass SeetCode Egalisierte XOR-Lösung noch besser ist und schneller

generasacodicetagpre.

Answer 1

Lassen Sie uns ein einfacheres Beispiel verwenden, um die Tatsache zu überprüfen.

Angenommen, $ n= 1 $ , d. H. Wir erhalten ein Array, das eine (unterschiedliche) Zahl enthält, die von 0, 1 entnommen wird.

.
• Wenn die angegebene Zahl 0 ist, muss die fehlende Nummer $ 1= 1 \ land0 $ sein.
• Wenn die angegebene Zahl 1 ist, muss die fehlende Zahl $ 0= 1 \ land1 $ sein.

zum zusammenfassen, wenn die angegebene Nummer $ A $ ist, dann ist die fehlende Nummer $ 1 \ land a= n \ Land A \ NOT= 0 \ Land A $ .

---

Was sind die grundlegenden Gründe für diese Magie in allgemeinen Situationen?

Es schaltet den Bitwise-XOR-Bediener aus, der häufig von " in der Programmiersprache"> $ \ Land $ "bezeichnet wird, verhält sich in der Programmiersprachen wie der gewöhnliche Plus-Bediener.

.
• es ist commutative und assoziativ . Die Reihenfolge der Operationen spielt also überhaupt keine Rolle.
• $ 0 $ Funktionen als Null, dh $ a \ land 0= a $ . So $ 0 $ kann entfernt werden.
• $ a \ land a= 0 $ für jede Anzahl $ A $ . Wenn also dieselbe Nummer zweimal erscheint, stornieren sie sich gegenseitig.

außerhalb der Programmiersprachen, der Bitwise XOR wird häufiger als " $ \ oplus $ " geschrieben, wobei das Plus-Symbol " $ + $ " In der Mitte erinnert uns erinnert, dass es sich wie eine gewöhnliche Ergänzung verhält.

Betrachten Sie nun den Ausdruck, $$ (0 \ oplus1 \ oplus2 \ oplus3 \ cdoTs \ oplus n) \ oplus (A_0 \ oplus a_1 \ oplus a_2 \ cdoter \ oplus a_ { n-1}). $$ Wann immer es ein Paar derselben Nummer gibt, können wir sie entfernen. Alle Nummern werden also zwischeneinander abgebrochen, mit der Ausnahme der fehlenden Nummer, da diese fehlende Nummer die einzige Nummer ist, die in $$ 0 \ oplus1 \ oplus2 \ oplus3 \ cdots \ oplus n $ angezeigt wird $ aber nicht in $$ A_0 \ oplus a_1 \ oplus a_2 \ cdoter \ oplus a_ {n-1}. $$ so,

$$ (0 \ oplus1 \ oplus2 \ oplus3 \ cdsot \ oplus n) \ oplus (A_0 \ oplus a_1 \ oplus a_2 \ cdot \ oplus a_ {n-1})=Text {die fehlende Nummer} $$

Lassen Sie uns die Reihenfolge der "Summation" auf der linken Seite ändern. Wir können paar $ 0 $ mit $ A_0 $ , $ 1 $ $ mit $ A_1 $ , $ 2 $ mit $ A_2 $ , $ \ CDS $ , $ n-1 $ mit $ A_ {N-1} $ , einfach nur $ n $ ungepaart. Wir sehen, dass die linke Seite ist $$ (0 \ oplus a_0) \ oplus (1 \ oplus a_1) \ oplus (2 \ oplus a_2) \ oplus \ cdoten (n-1 \ oplus a_ {n-1} ) \ oplus n. $$ Mach nun einfach $ n $ an der Vorderseite des Ausdrucks.

---

"Ich kann meinen Kopf einfach nicht umwickeln, warum wir die fehlende Variable mit einer Anordnung lang initialisieren müssen. Warum nicht mit null initialisieren, und wenn wir es mit null initialisieren, warum kann dieses algo das fehlende nicht finden Nummer? "

Es gibt nichts Besonderes über das Initialisieren der fehlenden Variablen mit $ n $ , der Anordnungsdauer. Sie können es sicherlich mit einer beliebigen Nummer initialisieren, einschließlich Null. Dann sollten Sie die verbleibenden -Nummern mit $ a_0, a_2, \ cdoten, a_ {n-1} $ ( willkürlich < / em> jede Zahl genau einmal). Zum Beispiel haben wir

$$ 0 \ oplus (1 \ oplus a_0) \ oplus (2 \ oplus a_1) \ oplus \ cdoten (n \ oplus a_ {n-1})=text { Die fehlende Zahl} $$

In der Tat müssen wir das Pairing überhaupt nicht tun. Wir können sogar direkte direkte $$ F (N)= 0 \ oplus1 \ oplus2 \ oplus3 \ cdots \ oplus n =Start {Hüllen} n & \ text {if} n= 0 \ pmod4 \\ 1 & \ text {if} n= 1 \ pmod4 \\ n + 1 & \ text {if} n= 2 \ pmod4 \\ 0 & \ Text {if} n= 3 \ pmod4 \\ \ ENDE {Hüllen} $$ und dann berechnen $$ F (n) \ oplus a_0 \ oplus a_1 \ oplus a_2 \ cdoter \ oplus a_ {n-1}, $$ das wird auch die fehlende Zahl ergeben. Daher haben wir das folgende schnellere Programm, um die fehlende Nummer zu berechnen.

generasacodicetagpre.

Der obige Ansatz ist sehr ähnlich zu Ansatz # 4 Gauß 'Formel auf Leetcode .

Answer 2

Beginnen Sie mit einer Liste von N-Ganzzahlen.Duplizieren Sie die Ganzzahlen und berechnen Sie den XOR, wenn diese 2n-Ganzzahlen.Was ist das Ergebnis?Ordnen Sie die 2N-Ganzzahlen in keiner Weise neu an und berechnen Sie ihren XOR.Was ist das Ergebnis?Entfernen Sie eine Nummer x aus der Liste und berechnen Sie den XOR.Was ist das Ergebnis?Entfernen Sie eine andere Nummer Y und berechnen Sie den XOR.Was ist das Ergebnis?

Gehen Sie jetzt zu Ihrem Problem zurück, und die Antworten, die Sie vorher gegeben haben, sagen Sie sofort, was Ihr Ergebnis sein wird.