Wenn ich dich richtig interpretiere, meinst du mit effektiv eigentlich effizient, also müssen wir die Zeit und Speicherkosten berücksichtigen. Wie sieht dein Array denn aus? Was mir jetzt auf die Schnelle einfällt wäre:
1. Die Reihenfolge der Elemente in der Liste darf nicht verändert werden.
-> 1.a Alle Elemente paarweise miteinander vergleichen und Duplikate markieren (Zwei verschachtelte for-Schleifen). Aufwand für das Finden der Duplikate = O(1) bzw. O(n) Speicherverbrauch, O(n²) Zeitaufwand.
-> 1.b Alle Elemente in eine zweite Liste kopieren und diese Liste wie in 2. verarbeiten: Aufwand für das Finden der Duplikate = O(n) Speicherverbrauch, O(n * log(n)) Zeitaufwand.
2. Die Reihenfolge der Elemente in der Liste darf verändert werden.
-> 2.a Die Liste sortieren (z.B. mit Heapsort oder Quicksort), danach stehen alle Duplikate hintereinander. Aufwand für das Finden der Duplikate = O(1) Speicherverbrauch, O(n * log(n)) Zeitaufwand.
3. Die Liste ist bereits zu jedem Zeitpunkt sortiert.
-> 3.a Alle Duplikate stehen bereits hintereinander.
4. ???
Nachdem jetzt alle Duplikate entweder markiert sind oder direkt hintereinander stehen, kannst du das Array von vorne nach hinten durchlaufen und die Elemente, die doppelt oder mehrfach vorkommen, in eine andere Liste verschieben. (Frage: verschieben von A nach B = Element aus Liste A löschen und in Liste B einfügen?)
Jetzt bleibt nur noch das Problem, dass man aus einer Arraybasierten Liste nicht effizient löschen/verschieben kann, da jede Löschaktion O(n) Zeit in Anspruch nimmt.
Ich häng mal noch diesen völlig ungetesteten Code an, vielleicht hilft der irgendwie (und wenns nur als Beispiel dient, wie man's nicht machen sollte ^^)
Gruß Dani
Dani H.
At Least I Can Say I Tried