Gegeben ein array von ganzen zahlen, finden Sie die erste ganze Zahl, die einzigartig ist
Gegeben ein array von ganzen zahlen, finden Sie die erste ganze Zahl, die einzigartig ist.
meine Lösung: verwenden Sie std::map
stellen integer (Zahl als Schlüssel, den index als Wert) eines (O(n^2 lgn))
, wenn Sie doppelte, entfernen Sie den Eintrag aus der map (O(lg n))
, nachdem man alle zahlen in der Karte, Durchlaufen Karte und den Schlüssel finden, mit dem kleinsten index O(n).
O(n^2 lgn)
weil die Karte braucht Sortierung zu tun.
Es ist nicht effizient.
andere bessere Lösungen?
- Wenn Sie sagen, "erste ganze Zahl, die einzigartig ist" meinst du den ersten Auftritt oder den kleinsten eine, oder Zufall?
- Das addieren aller zahlen in einer Karte ist
O(n log(n))
, nichtO(n^2 log(n))
. Jeder Einschub istO(log(n))
, und es gibtn
von Ihnen. - hat die neue Lösung matchup auf deine Frage, oder habe ich da etwas verpasst?
Du musst angemeldet sein, um einen Kommentar abzugeben.
Ich glaube, dass die folgenden wäre die optimale Lösung, zumindest basierend auf Raum /Zeit-Komplexität:
Schritt 1:
Speichern Sie die zahlen in einer hash-map, die hält, die integer als key und die Anzahl von Zeiten, es erscheint als Wert. Dies ist in der Regel eine O(n) Betrieb und die einfügen /Aktualisierung von Elementen in die Hashtabelle sollte konstant sein und Zeit, über dem Durchschnitt. Wenn eine ganze Zahl gefunden wird, erscheint mehr als zweimal, die Sie wirklich nicht haben, erhöhen Sie die Verwendungshäufigkeit weiter (wenn Sie nicht wollen).
Schritt 2:
Führen Sie einen zweiten Durchlauf über die zahlen. Suchen Sie jeweils bis in die hash map und die erste, die mit einem Auftritt von eins ist die, die Sie waren auf der Suche für (d.h., die erste single erscheinen integer). Dies ist auch O(n), so dass der gesamte Prozess O(n).
Einige mögliche Optimierungen für Besondere Fälle:
Optimierung Ein: kann Es möglich sein, durch ein einfaches array anstelle einer hash-Tabelle. Dies garantiert O(1) selbst im schlimmsten Fall zum zählen der Anzahl von vorkommen eines bestimmten integer-als auch bei der Suche sein Aussehen zählen. Auch dies erhöht die Echtzeit-performance, da der hash-Algorithmus nicht ausgeführt werden müssen. Es kann ein hit werden wegen der potentiell schlechteren Ort des Verweises (d.h., eine größere Datendichte Tabelle Vergleich der hash-Tabelle Durchführung mit einer angemessenen Auslastung). Dies wäre jedoch für sehr spezielle Fälle von ganzzahligen Ordnungen und kann gemildert werden, indem der hash-Tabelle, hash-Funktion, Herstellung von Pseudo-bucket-Praktika auf der Grundlage der eingehende ganze zahlen (D. H., schlechte Lokalität der Referenz zu beginnen).
Jedes byte des Arrays repräsentieren die Anzahl (bis 255) für die integer-vertreten durch den index dieses byte. Dies wäre nur möglich, wenn die Differenz zwischen dem niedrigsten integer und die höchsten (d.h. die Kardinalität der Domäne gültig sind Ganzzahlen) war klein genug, so dass dieses array würde passen in den Speicher. Der index in das array von einem bestimmten integer wäre sein Wert minus die kleinste ganze Zahl in der Datenbank.
Beispielsweise auf moderne hardware mit einem 64-bit OS, es ist durchaus denkbar, dass eine 4GB-array zugewiesen werden können, die die gesamte Domäne von 32-bit-Ganzzahlen. Auch größere arrays sind denkbar mit genügend Arbeitsspeicher.
Den kleinsten und den größten ganzen zahlen, müsste bekannt sein, bevor die Verarbeitung, oder anderen linearen Durchlauf durch die Daten mithilfe der minmax-Algorithmus, um herauszufinden, diese Informationen erforderlich sein würde.
Optimierung B: könnten Sie optimieren Optimierung weitere, durch die Verwendung von höchstens 2 bits pro integer (in Einem bit zeigt das Vorhandensein und die andere zeigt an, multiplizität). Dies würde es ermöglichen, für die Darstellung von vier Ganzzahlen, die pro byte, erweitern der array-Implementierung zum behandeln einer größeren Domäne von ganzen zahlen für eine bestimmte Menge des verfügbaren Speichers. Mehr-bit-Spiele können hier gespielt werden, komprimieren Sie die Darstellung weiter, aber Sie würden nur spezielle Fälle von kommenden Daten und kann daher nicht empfohlen werden, für die noch immer weitgehend Allgemeinen Fall.
All dies ohne Grund. Nur mit 2
for-loops
& eine variable geben würde, Sie eine einfacheO(n^2)
algo.Wenn Sie die Einnahme von all der Mühe, mit einer hash map, dann könnte es auch das sein, was @Michael Goldshteyn schlägt
UPDATE: ich weiß, diese Frage ist 1 Jahr alt. Aber war auf der Suche durch die Fragen, die ich beantwortet und stieß auf dieses. Dachte es gibt eine bessere Lösung als die Verwendung einer hashtable.
Wenn wir sagen einzigartig, wir haben ein Muster. ZB: [5, 5, 66, 66, 7, 1, 1, 77]. In diesem lässt sich bewegenden Fenster 3. betrachten Sie zuerst (5,5,66). wir können leicht Unternehmensgründung. dass es hier zu duplizieren. So verschieben Sie das Fenster um 1 element, so erhalten wir (5,66,66). Hier gilt das gleiche. weiter zur nächsten (66,66,7). Wieder dups hier. nächste (66,7,1). Keine dups hier! nehmen Sie das mittlere element, so ist dies der erste im set einzigartig. Der linken-element gehört zu den dup also könnte 1. Also 7 ist die erste eindeutige element.
Platz: O(1)
Zeit: O(n) * O(m^2) = O(n) * 9 ≈ O(n)
memmem()
diese einfache Lösung hat das Potenzial, schnell sein.Einfügen einer Karte ist
O(log n)
nichtO(n log n)
so einfügenn
Schlüsseln log n
. auch seine besser zu nutzenset
.O(n^2 log n)
der OP dachte, es zu sein, nichtO(n)
Obwohl es O(n^2), die folgende kleine Koeffizienten, nicht zu schlecht auf cache, und verwendet
memmem()
die ist schnell.array[1]
Aussehen die Antwort@user3612419