Ist es möglich, Duplikate in weniger als O (n) Zeit aus einer sortierten Liste zu entfernen?

Im Allgemeinen, nein. Stellen Sie sich eine Liste mit N Duplikaten vor. Sie müssten N-1 Entfernungen machen, also O (N).

Wenn Sie eine bestimmte Datenstruktur mit besser als O (1) Entfernung von Elementen angeben, gibt es möglicherweise einen besseren Weg für bestimmte Arten von Eingaben.

Auch wenn Sie eine Reihe von Elementen in O (1) effizient entfernen können, und es dauert O (1) Zeit, um ein Duplikat zu finden - stellen Sie sich eine Liste vor, wo es N / 2 Duplikatpaare gibt. Sie müssen immer noch N / 2 Suchen durchführen und N / 2 Bereiche entfernen, die beide O (N) sind.

(Es gibt auch ein bisschen Zweideutigkeit, da der Titel der Frage "Duplikate entfernen" ist, aber der Körper ist spezifisch für das Entfernen eines Bereichs)

Wenn die Liste, die sich aus Ihrer Sortierung ergibt, die folgende Repräsentation hat - jeder Knoten hat einen Wert und eine Anzahl von Auftritten dafür, dann wird die Entfernung der Duplikate für einen Wert die Anzahl für diesen Knoten trivialisch auf 1 setzen. (Eine Überspringungsliste hat wahrscheinlich ähnliche Eigenschaften, vorausgesetzt, es gibt eine annehmbare Umgebung, in der Müll gesammelt wird, in der keine Kosten für die Wiederherstellung von Speicher anfallen.) wäre O (1) für eine Verdopplung. Wenn Sie alle Duplikate aus der Liste entfernen müssen, wäre es immer noch O (N).

Im Allgemeinen gibt es das nicht, weil Sie immer einen Fall konstruieren können, in dem Sie O (n) haben (eine Liste ohne Duplikate). Wenn Sie jedoch anfangen, Annahmen über die Daten zu treffen (zum Beispiel, dass es höchstens logarithmische Elemente gibt), erhalten Sie möglicherweise etwas Besseres (ich bin mir in diesem Fall allerdings nicht sicher).

Dies setzt natürlich voraus, dass Sie eine Möglichkeit haben, effiziente "Massenentfernungen" durchzuführen, was bedeutet, dass Sie jeden Bereich gleicher Elemente in O (1) unabhängig von seiner Größe entfernen können.