Eine einzelne Zahl in einer Liste finden [Duplikat]

Question

Auf diese Frage gibt es hier bereits eine Antwort:

• So finden Sie die einzige Zahl in einem Array, die nicht zweimal vorkommt [Duplikat] 5 Antworten

Was wäre der beste Algorithmus, um eine Zahl zu finden, die nur einmal in einer Liste vorkommt, in der alle anderen Zahlen genau zweimal vorkommen?

In der Liste der Ganzzahlen (nehmen wir sie als Array) wiederholt sich also jede Ganzzahl bis auf eine genau zweimal.Welcher Algorithmus ist der beste, um diesen zu finden?

Answer 1

Der schnellste (O(n)) und speichereffizienteste (O(1)) Weg ist die XOR-Operation.

In C:

int arr[] = {3, 2, 5, 2, 1, 5, 3};

int num = 0, i;

for (i=0; i < 7; i++)
    num ^= arr[i];

printf("%i\n", num);

Dies gibt „1“ aus, was das einzige ist, das einmal vorkommt.

Dies funktioniert, weil beim ersten Drücken einer Zahl die Variable „num“ mit sich selbst markiert wird und beim zweiten Mal die Markierung von „num“ mit sich selbst aufgehoben wird (mehr oder weniger).Das Einzige, das nicht markiert bleibt, ist Ihr Nicht-Duplikat.

Answer 2

Übrigens können Sie diese Idee sehr schnell erweitern, um sie zu finden zwei eindeutige Nummern in einer Liste von Duplikaten.

Nennen wir die eindeutigen Zahlen a und b.Nehmen Sie zunächst das XOR von allem, wie Kyle vorgeschlagen hat.Was wir bekommen, ist a^b.Wir wissen a^b != 0, da a != b.Wählen Sie ein beliebiges Bit von a^b und verwenden Sie es als Maske – genauer gesagt:Wähle x als Potenz von 2, sodass x & (a^b) ungleich Null ist.

Teilen Sie nun die Liste in zwei Unterlisten auf – eine Unterliste enthält alle Zahlen y mit y&x == 0, und der Rest kommt in die andere Unterliste.Da wir x gewählt haben, wissen wir, dass a und b in unterschiedlichen Buckets liegen.Wir wissen auch, dass sich jedes Duplikatpaar immer noch im selben Bucket befindet.So können wir jetzt den alten „XOR-em-all“-Trick auf jeden Bucket unabhängig anwenden und herausfinden, was a und b vollständig sind.

Bam.

Answer 3

O(N)-Zeit, O(N)-Speicher

HT= Hash-Tabelle

Ht.clear () gehen Sie die Liste in die Reihenfolge für jeden von Ihnen angezeigten Element

if(HT.Contains(item)) -> HT.Remove(item)
else
ht.add(item)

Am Ende ist der Artikel im HT der Artikel, den Sie suchen.

Hinweis (Kredit @Jared Updike):Dieses System findet alle ungeraden Instanzen von Artikeln.

---

Kommentar:Ich verstehe nicht, wie die Leute für Lösungen stimmen können, die Ihnen NLogN-Leistung bieten.In welchem ​​Universum ist das „besser“?Ich bin noch mehr schockiert, dass Sie die NLogN-Lösung der akzeptierten Antwort markiert haben ...

Ich stimme jedoch zu, dass NLogN (bisher) die beste Lösung wäre, wenn der Speicher konstant sein muss.

Answer 4

Kyles Lösung würde offensichtlich keine Situationen erfassen, in denen der Datensatz nicht den Regeln entspricht.Wenn alle Zahlen paarweise wären, würde der Algorithmus ein Ergebnis von Null liefern, also genau den gleichen Wert, als ob Null der einzige Wert wäre, der nur einmal vorkommt.

Wenn es mehrere Einzelvorkommenswerte oder Tripel gäbe, wäre das Ergebnis ebenfalls ein Fehler.

Das Testen des Datensatzes kann durchaus zu einem kostspieligeren Algorithmus führen, sei es hinsichtlich des Speichers oder der Zeit.

Die Lösung von Csmba zeigt zwar einige Fehlerdaten (kein oder mehr als einen einzelnen Vorkommenswert), andere jedoch nicht (Vierpaare).In Bezug auf seine Lösung sind je nach Implementierung von HT entweder Speicher und/oder Zeit größer als O(n).

Wenn wir uns über die Richtigkeit des Eingabesatzes nicht sicher sein können, wäre das Sortieren und Zählen oder die Verwendung einer Hash-Tabelle zum Zählen von Vorkommnissen möglich, wobei die ganze Zahl selbst der Hash-Schlüssel ist.

Answer 5

Ich würde sagen, dass es eine gute Möglichkeit ist, einen Sortieralgorithmus zu verwenden und dann die sortierte Liste durchzugehen, um die Zahl zu finden.

Und jetzt besteht das Problem darin, den „besten“ Sortieralgorithmus zu finden.Es gibt viele Sortieralgorithmen, jeder davon hat seine Stärken und Schwächen, daher ist dies eine ziemlich komplizierte Frage.Der Wikipedia-Eintrag Scheint eine gute Informationsquelle dazu zu sein.

Answer 6

Implementierung in Ruby:

a = [1,2,3,4,123,1,2,.........]
t = a.length-1
for i in 0..t
   s = a.index(a[i])+1
   b = a[s..t]
   w = b.include?a[i]
   if w == false
       puts a[i]
   end
end

Answer 7

Sie müssen angeben, was Sie unter „am besten“ verstehen – für einige zählt nur die Geschwindigkeit und würde eine Antwort als „am besten“ qualifizieren – für andere verzeihen sie möglicherweise ein paar hundert Millisekunden, wenn die Lösung besser lesbar wäre.

„Am besten“ ist subjektiv, es sei denn, Sie machen genauere Angaben.

---

Das gesagt:

Gehen Sie die Zahlen durch, durchsuchen Sie für jede Zahl die Liste nach dieser Zahl und wenn Sie die Zahl erreichen, die nur eine 1 für die Anzahl der Suchergebnisse zurückgibt, sind Sie fertig.

Answer 8

Scheint, als ob das Beste, was Sie tun können, darin besteht, die Liste zu durchlaufen, jedes Element einer Liste der „gesehenen“ Elemente hinzuzufügen oder es aus der Liste „Gesehen“ zu entfernen, wenn es bereits vorhanden ist, und am Ende Ihre Liste der „Gesehenen“ zu erstellen „Elemente enthalten das singuläre Element.Dies ist O(n) in Bezug auf die Zeit und n in Bezug auf den Raum (im schlimmsten Fall ist es viel besser, wenn die Liste sortiert ist).

Die Tatsache, dass es sich um ganze Zahlen handelt, spielt keine Rolle, da man mit der Addition nichts Besonderes machen kann ...ist da?

Frage

Ich verstehe nicht, warum die ausgewählte Antwort in jeder Hinsicht „am besten“ ist.O(N*lgN) > O(N), und es ändert die Liste (oder erstellt eine Kopie davon, was räumlich und zeitlich immer noch teurer ist).Vermisse ich etwas?

Answer 9

Hängt jedoch davon ab, wie groß/klein/verschieden die Zahlen sind.Möglicherweise wäre eine Basissortierung anwendbar, die die Sortierzeit der O(N log N)-Lösung um ein Vielfaches verkürzen würde.

Answer 10

Die Sortiermethode und die XOR-Methode haben die gleiche Zeitkomplexität.Die XOR-Methode ist nur O(n), wenn Sie davon ausgehen, dass die bitweise XOR-Verknüpfung zweier Zeichenfolgen eine Operation mit konstanter Zeit ist.Dies entspricht der Aussage, dass die Größe der Ganzzahlen im Array durch eine Konstante begrenzt ist.In diesem Fall können Sie die Radix-Sortierung verwenden, um das Array in O(n) zu sortieren.

Wenn die Zahlen nicht begrenzt sind, benötigt das bitweise XOR die Zeit O(k), wobei k die Länge der Bitfolge ist und die XOR-Methode O(nk) benötigt.Jetzt sortiert die Radix-Sortierung das Array erneut in der Zeit O(nk).

Answer 11

Sie könnten einfach die Elemente in der Menge in einen Hash einfügen, bis Sie eine Kollision finden.In Ruby ist dies ein Einzeiler.

def find_dupe(array)
  h={}
  array.detect { |e| h[e]||(h[e]=true; false) }
end

Also, find_dupe([1,2,3,4,5,1]) würde 1 zurückgeben.

Dies ist jedoch tatsächlich eine häufige „Trickfrage“ in Vorstellungsgesprächen.Normalerweise handelt es sich um eine Liste aufeinanderfolgender Ganzzahlen mit einem Duplikat.In diesem Fall verlangt der Interviewer häufig, dass Sie die Gaußsche Summe von verwenden N-Integer-Trick, z.B. n*(n+1)/2 von der tatsächlichen Summe abgezogen.Die Lehrbuchantwort lautet in etwa so.

def find_dupe_for_consecutive_integers(array)
  n=array.size-1   # subtract one from array.size because of the dupe
  array.sum - n*(n+1)/2
end