Wenn wir ein Array haben, das Nummern enthält, die dort zweimal auftritt, und eine Zahl, die nur einmal vorkommt, können wir XOR-Operator verwenden, um es aufgrund der Kommunikationen zu finden Recht. zFinden Sie die Nummer in Array nur einmal mit bitweisen Operatoren
1 2 3 2 3
1^2^3^2^3 = (2^2)^(3^3)^1 = 1
Aber können wir bitweise Tricks anwenden, um die Nummer zu finden, die einmal in Array occures wenn andere Zahlen n mal occure können, n> 1?
Mit bitweisen Operatoren, nein, nur wenn n immer gerade ist.
Aber es gibt viele andere Methoden, die verwendet werden können, wie das Sortieren und Scannen nach einem Element, das einmal auftritt, oder das Zuweisen jedes Elements zu Buckets, wenn die Eingabedomäne irgendwie eingeschränkt ist.
Als Beispiel für den ersten:
def findASingle(list):
if list length is zero:
return nothing
if list length is one:
return first item in list
sort list
for each item in last other than first and last:
if item is different to both previous and next item:
return item
Und für die zweite, es ist beschränkt auf (zum Beispiel) einstelligen nicht negativen ganzen Zahlen unter der Annahme:
def findASingle(list):
create count[0..9], all set to zero
for each item in last:
count[item] = count[item] + 1
for each index 0 through 9 inclusive:
if count[index] is 1:
return index
return nothing
Es gibt einen Weg zu tun, aber nicht mit binären Operatoren. Sie können jede Zahl als einen Vektor von Bits darstellen und dann alle Vektoren zusammen summieren (mod n). Der resultierende Vektor wird diese eindeutige Zahl darstellen.
Zum Beispiel Betrachten wir n = 3 und Sequenz 2 3 5 2 5 5 2
Vektoren sind: [0 1 0], [0 1 1], [1 0 1], [0 1 0], [1 0 1], [1 0 1], [0 1 0]
Per-Element Summe aus Alle Vektoren sind: [3 4 4]
Mod 3, die sein wird: [0 1 1] was zu 3 - einzigartiges Element in der Sequenz.
Dies ist eine Verallgemeinerung von XOR Trick; tatsächlich ist XOR genau diese Operation - Summierung in Mod 2.
Ziemlich sicher, dass es nur funktioniert, wenn 'n% 2 == 0'. – NathanOliver
@NathanOliver Ja, sie heben sich nur gegenseitig auf, wenn sie paarweise kommen. Es ist, als ob man negative Zahlen multipliziert: 2, 4 oder 6 negative Zahlen ergeben eine positive Zahl, da sich die Zeichen gegenseitig aufheben. 3, 5 oder 7 negative Zahlen haben jeweils ein "baumelndes" Negativ, das seinen Weg zum endgültigen Ausgang findet. – Dan