Ich habe diese Frage für eine Prüfung:
Geben Sie ein gegebenes Integer-Array an, um die erste Zahl zu finden, die sich im Array nicht wiederholt, wobei die O (N) -Zeitkomplexität und die O (1) -Komplexität verwendet werden.
Ich konnte mir keine Lösung vorstellen. Ich weiß, dass ich über das Array iterieren kann und eine Linkedhashmap pflegen kann, die sowohl das Array-Element als auch die Anzahl der Male, die es erscheint, speichert, und dann muss ich hashmap suchen, um diese Nummer zu finden. Raumkomplexität ist größer als O (1), aber ich konnte mir keine andere Lösung vorstellen.
Ich lese auch das Problem sorgfältig und sagte, dass die maximale Größe des Arrays 1 Million wäre. Ich denke, wenn wir eine benutzerdefinierte hashmap erstellen können, die ein Array fester Größe von 1 Million Größe verwenden wird, dann kann dies in O (1) Raumkomplexität erreicht werden, da in diesem Fall Speicherbedarf konstant wäre, aber sicher, wenn ich richtig bin. Bitte lassen Sie mich wissen, ob es eine andere Lösung gibt.
Wenn es genau ZWEI (oder in Vielfachen von 2) Einträgen für alle Elemente außer einem Element gibt, das sich nicht wiederholt, können Sie den XOR-Operator verwenden.
Beispiel:
%Vor% Jede mit XOR verknüpfte Zahl ist 0. Wenn also eine Zahl zweimal erscheint, ist sie 0 im gesamten XOR-Ergebnis, so dass nur die sich nicht wiederholende Zahl in x übrig bleibt.
Hinweis: Wenn Sie 1 Million Zahlen haben, muss die Variable zum Speichern des XOR-Ergebnisses groß genug sein.
Um die erste sich nicht wiederholende Zahl in einem gegebenen Integer-Array zu finden
UPDATE: Eine bessere Lösung gefunden.
Ich denke, wir können es in O(n) zeitlicher Komplexität mit einer zusätzlichen Datenstruktur wie HashMap lösen. Iterieren durch das Array und fügen das Element als Schlüssel und die Indexposition des Elements im Array als Wert in der Map ein. Wenn der Schlüssel bereits vorhanden ist, kann entweder das Schlüssel / Wert-Paar entfernt oder der Wert auf -1 gesetzt werden.
Sobald das gesamte Array durchlaufen ist, können wir das keySet () aus der hashmap holen und dann den Schlüssel finden, der den niedrigsten Wert hat (ignore -1).
also wäre das so
Zeitkomplexität: O (N)
Raumkomplexität: O (N)
Alte Lösung: Wir können dies lösen, indem wir ein anderes Array erstellen, das durch Sortieren des gegebenen Arrays erhalten wird. Dies würde O(nlogn) time benötigen.
dann können wir jedes Element im angegebenen Eingabe-Array durchlaufen, versuchen, das Element & amp; Vergleiche mit dem nächsten Element im sortierten Array, wenn wiederholt für das nächste Element in einem gegebenen Array fortgesetzt wird, wenn nicht wiederholt, dann haben wir das erste sich nicht wiederholende Element in einem gegebenen Eingabearray von ganzen Zahlen gefunden.
Zeitkomplexität: O (nlogn)
Raumkomplexität: O (n)
P.S .: Es tut mir leid, ich habe nicht alle Kommentare gelesen, James Kanze hat diese Lösung bereits in Kommentaren, Dank an ihn geliefert.
Ich glaube, der Trick zur Lösung des Problems ist:
Maximale Größe des Arrays wäre 1 Million
seit:
O (1) Leerzeichen bedeutet, dass der vom Algorithmus benötigte Speicher konstant
ist
dann wird die Raumkomplexität automatisch zu O (1) angesichts der Konstante 1M. HINWEIS. 1M ist immer noch eine konstante Zahl, obwohl es eine sehr große Zahl ist. Daher müssen wir uns nur auf die zeitliche Komplexität konzentrieren.
Unter Verwendung von LinkedHashMap können wir ein neues Element mit O(1) hinzufügen und Element mit O(1) abrufen. Das Aktualisieren eines Eintrags dauert also auch O (1). es auch preserves the order . Daher können wir den frühesten Eintrag finden
Dann wird das Problem in zwei Schritten einfach:
jeder der obigen Schritte benötigt O (n), also insgesamt time complexity ist O(2n) = O(n) .