Finden Sie das eine sich nicht wiederholende Element im Array?

Question

Ich habe ein Array von n Elementen, in denen nur ein Element nicht wiederholt wird, sonst werden alle anderen Zahlen> 1 mal wiederholt. Und es gibt keine Grenze für die Reichweite der Zahlen im Array.

Einige Lösungen sind:

• Die Nutzung von Hash, aber, dass in der linearen Zeit Komplexität führen würde, aber sehr schlechte Raum Komplexität
• die Liste Sortierung mit MergeSort O(nlogn) und dann das Element zu finden, was nicht wiederholt

Gibt es eine bessere Lösung?

Answer 1

Ein allgemeiner Ansatz besteht darin, eine Bucketing-Technik zu implementieren (deren Hashing eine solche Technik ist), um die Elemente unter Verwendung ihrer Identität (z. B. Index) in verschiedene "Buckets" zu verteilen und dann den Bucket mit der kleinsten Größe zu finden dein Fall). Dieses Problem ist meines Erachtens auch als Problem der Minoritätselemente bekannt. Es wird so viele Eimer geben, wie es einzigartige Elemente in Ihrem Set gibt.

Das Ausführen von Hashing ist aufgrund von Kollisionen problematisch und wie Ihr Algorithmus damit umgehen könnte. Bestimmte assoziative Array-Ansätze wie Versuche und erweiterbares Hashing scheinen nicht zu gelten, da sie besser für Strings geeignet sind.

Eine Anwendung der oben genannten ist die Union-Find data structure. Ihre Sets werden die Buckets sein, und Sie müssen MakeSet() und Find() für jedes Element in Ihrem Array zu einem Preis von $ O (\ alpha (n)) $ pro Aufruf aufrufen, wobei $ \ alpha (n) $ ist die extrem langsam wachsende inverse Ackermann-Funktion. Sie können sich vorstellen, dass es effektiv eine Konstante ist.

Sie müssen Union tun, wenn ein Element bereits existiert. Mit einigen Änderungen, um den Satz mit minimaler Kardinalität zu verfolgen, sollte diese Lösung funktionieren. Die zeitliche Komplexität dieser Lösung ist $ O (n \ alpha (n)) $.

Ihr Problem scheint auch lose mit der Element Uniqueness problem verwandt zu sein.

Answer 2

Versuchen Sie ein Multi-Pass-Scannen, wenn Sie eine strikte Platzbeschränkung haben.

Angenommen, die Eingabe hat n Elemente und Sie können nur m Elemente in Ihrem Speicher halten. Wenn Sie einen Hash-Tabellen-Ansatz verwenden, müssen Sie im schlimmsten Fall mit n/2 eindeutigen Zahlen umgehen, so dass Sie m> n/2 wollen. Falls Sie dieses große m nicht haben, können Sie n Elemente in k = (max (input) -min (input))/(2m) Gruppen partitionieren und die n Eingabeelemente k mal scannen (im schlimmsten Fall) Fall):

1st run: nur Hash-get/put/mark/was auch immer Elemente mit Wert < min (Eingang) + m * 2; denn im Bereich (min (Eingabe), min (Eingabe) + m * 2) gibt es höchstens m eindeutige Elemente, mit denen man umgehen kann. Wenn Sie Glück haben, finden Sie das Einzigartige bereits, ansonsten fahren Sie fort.

2. Lauf: Nur auf den Elementen mit dem Wert im Bereich arbeitet (min (Eingang) + m * 2, min (Eingang) + m * 4) und so weiter, so weiter

Auf diese Weise, Sie beeinträchtigen die Zeitkomplexität zu einem O (kn), aber Sie einen Raum Komplexität von O (m)

Answer 3

Zwei Ideen kommen mir in den Sinn gebunden bekommen:

• A smoothsort eine bessere Alternative sein kann als der zitierte Mergesort für Ihre Bedürfnisse, da O (1) im Speicher verwendet wird, O (nlogn) im schlimmsten Fall e wie die Merge-Sortierung aber im besten Fall O (n);

• Basierend auf der (rückwärts) Idee der splay tree, könnten Sie eine Art von Baum zu machen, die die Blätter in Richtung der Unterseite schieben würden, sobald sie (statt nach oben, wie in dem gespreizten Baum) verwendet werden. Dies würde Ihnen immer noch eine O (nlogn) -Implantation der Sorte geben, aber der Vorteil wäre der O (1) Schritt, das einzigartige Element zu finden, es wäre die Wurzel. Der Sortieralgorithmus ist die Summe O (n log n) + O (n), und dieser Algorithmus würde O (n log n) + O (1)

anders sein, wie sie angegeben ist, eine Hash-basierte Lösung verwendet (wie Hash-implementierter Satz) würde zu einem O (n) -Algorithmus führen (O (n) zum Einfügen und Hinzufügen einer Zählreferenz und O (n) zum Durchlaufen Ihrer Menge, um das einzigartige Element zu finden), aber Sie schienen die Erinnerung nicht zu mögen Nutzung, obwohl ich nicht weiß warum. Speicher ist billig, in diesen Tagen ...