Die Verwendung des XOR-Operators zum Suchen nach doppelten Elementen in einem Array schlägt in vielen Fällen fehl

Von der ursprünglichen Frage:

  

Angenommen, Sie haben ein Array von 1001 Ganzzahlen. Die ganzen Zahlen sind in zufälliger Reihenfolge, aber Sie wissen, dass jede der ganzen Zahlen zwischen 1 und 1000 (einschließlich) liegt. Darüber hinaus wird jede Zahl nur einmal im Array angezeigt, mit Ausnahme einer Nummer, die zweimal auftritt.

Es besagt grundsätzlich, dass dieser Algorithmus nur funktioniert, wenn Sie aufeinanderfolgende Ganzzahlen haben, beginnend mit 1 und mit einigen N endet.

Wenn Sie es in einen allgemeineren Fall ändern wollen, müssen Sie folgende Dinge tun:

Finde Minimum und Maximum im Array. Berechnen Sie dann die erwartete Ausgabe (x oder alle ganzen Zahlen zwischen Minimum und Maximum). Dann berechne xor aller Elemente im Array. Dann xor diese zwei Dinge und Sie erhalten eine Ausgabe.

Eine XOR-Anweisung hat die Eigenschaft, dass 'ein' XOR 'a' immer 0 ist, das heißt, sie werden gelöscht. Wenn Sie also wissen, dass Ihre Liste nur ein Duplikat hat und der Bereich x zu y ist, 601 bis 607 in Ihrem Fall ist es möglich, die xor aller Elemente von x bis y in einer Variablen zu halten, und dann x oder diese Variable mit allen Elementen, die Sie in Ihrem Array haben. Da es nur ein Element geben wird, das dupliziert werden soll, wird es aufgrund der xor-Operation nicht gelöscht und das wird deine Antwort sein.

Dieser Code gibt den Ausgang 605, wie gewünscht!

Hier ist der in der ursprünglichen Frage gezeigte Code, der sich von Ihrer Implementierung unterscheidet. Sie haben es geändert, um eine lokale Variable anstelle des letzten Elements des Arrays zu verwenden, das einen Unterschied macht:

// ODER Sie können HashTable und Hash-Funktion verwenden, wenn Sie das gleiche
eingeben Wert in die Hash-Tabelle, dass Sie zählen können, wenn es größer ist als
Ein Wert bei einem bestimmten Index von HashTable, dann können Sie sagen, dass es im Array wiederholte Werte gibt.