Finden von Paaren mit kleinsten XOR-Werten aus einer Liste

Das Sortieren der Zahlen in der richtigen Reihenfolge wäre ein Anfang, da der Unterschied zwischen den Paaren eine untere Grenze für den Xor und damit einen Grenzwert für den Zeitpunkt gibt, an dem keine Zahlen mehr nach x oder x gesucht werden.

Es gibt auch eine Abkürzung, um nach Zahlenpaaren zu suchen, deren xor kleiner als (sagen wir) eine Potenz von 2 ist, weil Sie nur an x ​​interessiert sind & lt; = y & lt; = x | (2 ^ N - 1). Wenn dies Ihnen nicht genug Paare gibt, erhöhen Sie N und versuchen Sie es erneut.

EDIT: Sie können natürlich die Zahlenpaare ausschließen, die Sie bereits gefunden haben, deren xor kleiner ist als die vorherige Potenz von 2, indem Sie x | verwenden (2 ^ (N - 1) - 1) & lt; y & lt; = x | (2 ^ N) - 1.

Beispiel basierend auf (sortiert) [1, 2, 2, 3, 4]

Beginnen Sie mit der Suche nach Zahlenpaaren, deren xor kleiner als 1 ist: Suchen Sie für jede Zahl x nach folgenden Zahlen y = x. Dies ergibt {2, 2}.

Wenn Sie mehr als ein Paar benötigen, suchen Sie nach Paaren von Zahlen, deren xor kleiner als 2, aber nicht kleiner als 1 ist: Suchen Sie für jede Zahl x nach Zahlen x & lt; y & lt; = x | 1. Dies ergibt {2, 3} (zweimal).

Beachten Sie, dass die endgültigen XOR-Werte nicht richtig sortiert sind, aber jeder Batch ist strikt kleiner als der vorherige Batch.

Wenn Sie mehr als das brauchen, suchen Sie nach Zahlenpaaren, deren xor kleiner als 4, aber nicht kleiner als 2 ist: Suchen Sie für jede Zahl x nach Zahlen x | 1 & lt; y & lt; = x | 3. Dies ergibt {1, 2} (zweimal); {1, 3}.

Wenn Sie mehr brauchen, suchen Sie nach Zahlenpaaren, deren xor kleiner als 8, aber nicht kleiner als 4 ist: Suchen Sie für jede Zahl x nach Zahlen x | 3 & lt; y & lt; = x | 7. Dies ergibt {1, 4}; {2, 4} (zweimal); {3, 4}.

Beachten Sie, dass, wenn alle Bits links von bit n (von rechts gezählt) der Zahlen x und y gleich sind, x xor y ≤ 2 ⁿ -1

Dies kann ausgenutzt werden, indem man jede Zahl in einem bitweisen-trie speichert - das heißt, ein Trie, wo jeder edge ist entweder ein 0 oder ein 1 . Dann x xor y ≤ 2 ^{d (x, y)} -1, wobei d(x,y) die Anzahl der Schritte ist, um nach dem kleinsten gemeinsamen Vorfahren von x und% co_de zu suchen %.

Sobald Sie den Trie haben, ist es einfach, alle Paare wie y zu finden - navigieren Sie einfach zu allen Knoten 1 über den Blättern und vergleichen Sie jeden der Knoten dieses Knotens miteinander. Diese Werte geben Ihnen ein Maximum d(x,y) = 1 von 2 ¹ -1 = 1.

Wenn Sie immer noch keine x xor y -Werte haben, dann bewegen Sie sich zu allen Knoten 2 Ebenen über den Blättern und vergleichen Sie die Enkelkinder jedes Knotens miteinander ^† . Diese Werte geben Ihnen ein Maximum k von 2 ² -1 = 3.

^† (Sie müssen eigentlich nur jedes der Blätter im linken Teilbaum mit jedem der Blätter im rechten Teilbaum vergleichen, da jedes der Blätter in einem gegebenen Teilbaum wurden bereits miteinander verglichen)

Fahren Sie fort, bis Sie nach dem Überprüfen aller Knoten für eine bestimmte Ebene mindestens x xor y -Werte von k haben. Dann sortiere diese Liste von Werten und nimm die x xor y am kleinsten.

Wenn k klein ist (& lt; n ² ), ist dieser Algorithmus O (n) . Für große k ist es O (2 ^b n) , wobei b die Anzahl der Bits pro Integer ist (angenommen Es gibt nicht viele Duplikate) .

Ich würde das angehen, indem ich zuerst das Eingabearray von ganzen Zahlen sortiere. Dann sind die Paare mit den kleinsten xor-Werten nebeneinander (aber nicht alle benachbarten Paare haben die kleinsten xor-Werte). Sie können mit benachbarten Paaren beginnen, dann nach außen arbeiten und Paare (N, N + 2), (N, N + 3) prüfen, bis Sie die gewünschte Liste mit den kleinsten K Ergebnissen erreicht haben.

Für das Beispiel-Array {1 3 2 4 2} ist das sortierte Array {1 2 2 3 4} und die paarweisen xor-Werte sind:

Für den nächsten Schritt,

und wieder

endlich,

Diese Idee ist nicht vollständig, aber Sie sollten in der Lage sein, damit eine vollständige Lösung zu erstellen.