Wie finde ich den Index der doppelten Elemente in C ++?

Effizient könnten Sie std::unordered_set verwenden (um doppelte Indizes eindeutig zu verfolgen) und std::unordered_map (um eindeutige Zahlen und ihre Indizes zu verfolgen).

Dies geschieht in O(N * [O(1) + ... + O(1)]) ... ungefähr = O(N) :

Erläuterung:

Gegeben ein Array A

• Verwenden Sie eine Reihe eindeutiger Indizes, rtn .

• Verwenden einer KV (Schlüsselwert) -Karte, dup ; Dabei ist k ein Element im Array A und v ist der Index dieses Elements im Array.

• Für jedes Element a mit dem Index i im Array:

  • finde kv wenn a existiert als k in dup
  • Wenn es existiert,
    • Fügen Sie i in rtn ein
    • Fügen Sie v in rtn ein
  • Andernfalls: a und i als kv in dup
• gibt rtn zurück

Siehe ein vollständiges Beispiel: Live auf Coliru .

Für eine Eingabe von:

Wir haben eine Ausgabe von:

Wieder,

Für eine Eingabe von:

Wir haben eine Ausgabe von:

Wenn Sie die Indizes in der richtigen Reihenfolge benötigen, können Sie das resultierende Array einfach sortieren.

Ich glaube nicht, dass es einen Standard-STL-Weg gibt, dies zu tun. Hier ist eine O (N * N) Lösung:

Ein Ansatz, der auf der Sortierung basiert, könnte sich für längere Arrays als effizienter erweisen: Sie müssten jedoch eine Tabelle mit einer neuen Position erstellen - & gt; alte Position, um die Indizes der doppelten Elemente zu erhalten.

Meine zwei Cent hierauf. Nicht ganz sicher über das große O dieses hier (sieht für mich wie O (N) aus):

  

Probieren Sie es online aus!