Wie entfernt man doppelte Elemente in einem Array in O (n) in C oder C ++?

Der beste Fall ist O(n log n) . Führen Sie eine Heap-Sortierung für das ursprüngliche Array durch: O(n log n) in time, O(1) / in-place im Space. Dann durchlaufen Sie das Array nacheinander mit 2 Indizes (Quelle und Ziel), um die Wiederholungen zu reduzieren. Dies hat den Nebeneffekt, dass die ursprüngliche Reihenfolge nicht beibehalten wird, aber da "Duplikate entfernen" nicht angibt, welche Duplikate entfernt werden sollen (zuerst? Sekunde? Letzte?), Hoffe ich, dass es Ihnen egal ist, dass die Reihenfolge verloren geht .

Wenn Sie die ursprüngliche Reihenfolge beibehalten möchten, gibt es keine Möglichkeit, Dinge an Ort und Stelle zu erledigen. Aber es ist trivial, wenn Sie ein Array von Zeigern auf Elemente im ursprünglichen Array erstellen, alle Ihre Arbeit an den Zeigern ausführen und sie verwenden, um das ursprüngliche Array am Ende zu reduzieren.

Jeder, der behauptet, dass es in O(n) time und in-place gemacht werden kann, ist einfach falsch, modulo einige Argumente darüber, was O(n) und In-Place bedeuten. Eine offensichtliche Pseudolösung, wenn Ihre Elemente 32-Bit-Integer sind, besteht darin, ein 4-Gigabit-Bit-Array (512 Megabyte) zu verwenden, das nur auf Nullen initialisiert wird, wenn Sie diese Zahl sehen und überspringen das Bit war schon an. Natürlich nutzt man dann die Tatsache aus, dass n durch eine Konstante begrenzt ist, also ist technisch alles O(1) , aber mit einem schrecklichen konstanten Faktor. Allerdings erwähne ich diesen Ansatz, da, wenn n durch eine kleine Konstante begrenzt ist - zum Beispiel, wenn Sie 16-Bit-Ganzzahlen haben - es eine sehr praktische Lösung ist.

Ja. Da der Zugriff (Einfügung oder Suche) auf einer Hashtabelle O (1) ist, können Sie Duplikate in O (N) entfernen.

Pseudocode:

Das ist O (N).

Einige Kommentatoren haben darauf hingewiesen, dass die Frage, ob eine Hashtabelle O (1) ist, von einer Reihe von Dingen abhängt. Aber in der realen Welt, mit einem guten Hash, können Sie konstante Leistung erwarten. Und es ist möglich, einen Hash zu erstellen, der O (1) ist, um die Theoretiker zu befriedigen.

Ich werde eine Variation von Borealids Antwort vorschlagen, aber ich werde vorne darauf hinweisen, dass es betrügt. Im Grunde funktioniert es nur unter der Annahme, dass die Werte im Array stark eingeschränkt sind - z. dass alle Schlüssel 32-Bit-Ganzzahlen sind.

Anstelle einer Hash-Tabelle sollte ein Bitvektor verwendet werden. Dies ist eine O (1) Speicheranforderung, die Rahul theoretisch glücklich machen sollte (aber nicht). Mit den 32-Bit-Ganzzahlen benötigt der Bitvektor 512 MB (dh 2 ** 32 Bits) - unter der Annahme von 8-Bit-Bytes, wie einige Pedanten aufzeigen können.

Wie Borealid darauf hinweisen sollte, ist eine Hashtabelle - nur mit einer trivialen Hash-Funktion. Dies garantiert, dass es zu keinen Kollisionen kommt. Die einzige Möglichkeit für eine Kollision besteht darin, dass Sie im Eingabe-Array zweimal den gleichen Wert haben. Da der zweite Punkt jedoch ignoriert werden soll, spielt dies keine Rolle.

Pseudocode für Vollständigkeit ...

Um wirklich albern zu sein (aber theoretisch korrekt), werde ich auch darauf hinweisen, dass der Platzbedarf immer noch O (1) ist, selbst wenn das Array 64-Bit-Ganzzahlen enthält. Der konstante Ausdruck ist ein bisschen groß, stimme ich zu, und Sie können Probleme mit 64-Bit-CPUs haben, die nicht die vollen 64 Bits einer Adresse verwenden können, aber ...

Nimm dein Beispiel. Wenn die Array-Elemente eine ganze Zahl enthalten, können Sie ein Nachschlage-Bit-Array erstellen.

Wenn Sie eine Ganzzahl wie 3 finden, schalten Sie das 3. Bit ein. Wenn Sie eine Ganzzahl wie 5 finden, schalten Sie das fünfte Bit ein.

Wenn das Array Elemente anstelle von Ganzzahlen enthält oder das Element nicht gebunden ist, wäre die Verwendung einer Hashtabelle eine gute Wahl, da Hashtabellen-Suchkosten eine Konstante sind.

Die kanonische Implementierung des unique() -Algorithmus sieht ungefähr wie folgt aus:

Dieser Algorithmus verwendet eine Reihe von sortierten Elementen. Wenn der Bereich nicht sortiert ist, sortieren Sie ihn, bevor Sie den Algorithmus aufrufen. Der Algorithmus wird in-Place ausgeführt und gibt einen Iterator zurück, der auf das Element "one-past-the-last" der eindeutigen Sequenz zeigt.

Wenn Sie die Elemente nicht sortieren können, haben Sie sich selbst in die Ecke gedrängt und Sie haben keine andere Wahl, als einen Algorithmus mit einer Laufzeitleistung schlechter als O (n) zu verwenden.

Dieser Algorithmus läuft in O (n) Laufzeit. Das ist groß - oh n, schlimmstenfalls in allen Fällen, nicht amortisierte Zeit. Es verwendet O (1) Leerzeichen.

Das von Ihnen angegebene Beispiel ist ein sortiertes Array. Es ist nur in diesem Fall möglich (angesichts Ihrer konstanten Platzbeschränkung)