Wie lösche ich eine verknüpfte Liste in $ mathcal {o} (n log n) $ Zeit?

Question

Ich habe mich gefragt, wie man doppelte Werte aus einer verknüpften Liste in $ mathcal {o} (n lg n) $ time entfernen. Ich habe eine Idee, dass durch die Verwendung der Zusammenführungssorte, wenn wir Elemente für die Auswahl des Kleinen vergleichen möchten, wenn sie beim Zeiger gleichermaßen vorangetrieben werden, und nur ein Element in Betracht zu ziehen. Irgendwelche Alternativen?

Answer 1

1. Sortieren Sie die verknüpfte Liste in $ o (N log n) $ time.
2. Gehen Sie jedes Element der Liste in ihrer Bestellung durch und entfernen Sie das Element, wenn es mit dem vorherigen in $ O (n) $ TIME identisch ist.

Die Gesamtkomplexität beträgt $ o (n log n) $, wonach Sie suchen.

Answer 2

Sie können es in $ o (n) $ wie folgt tun.

1) Erstellen Sie eine Hash -Tabelle, indem Sie die verknüpfte Liste durchqueren und ihre Elemente in die Hash -Tabelle hinzufügen. Durchsuchen Sie in jeder Iteration die Hash -Tabelle nach dem aktuellen Element, das in der Iteration berücksichtigt wird. Wenn das Element nicht gefunden wird, fügen Sie der Hash -Tabelle den Elementwert als Schlüssel und 1 als entsprechender Wert hinzu. Wenn Sie stattdessen das Element finden (das in einer vorherigen Iteration eingefügt wurde), fügen Sie einfach 1 zum entsprechenden Wert hinzu und aktualisieren den Hash -Tabelleneintrag (korrekt aktualisiert die Element -Multiplizität). Am Ende wird Ihre Hash -Tabelle höchsten größer als eins. Dies dauert $ o (n) $ $, da in jedem der $ n $ iterations die Arbeiten an der Hash -Tabelle $ O (1) $ beträgt.

2) Überqueren Sie nun die Hash -Tabelle und erstellen Sie eine neue verknüpfte Liste, indem Sie einen Knoten für jedes gefundene Element hinzufügen. Dies dauert höchstens $ O (n) $, da die Hash -Tabelle höchsten (1) $.

Daher beträgt die Gesamtkomplexität höchstens $ o (n) $.