Remove Duplicates from Sorted Array

Q: Wie entfernst du Duplikate direkt, ohne zusätzlichen Speicherplatz zu verwenden?

Führe neben dem Leseindex einen Schreibindex k . Die ersten k Plätze enthalten die bisher unterschiedlichen Werte. Wenn sich der gelesene Wert von nums[k-1] unterscheidet, kopiere ihn nach nums[k] und erhöhe k . Der Schreibindex überschreitet niemals den Leseindex, sodass nichts überschrieben wird, bevor es gelesen wurde.

LeichtZwei Zeiger

+10

Du erhältst ein Array von Ganzzahlen nums, das in nicht absteigender Reihenfolge sortiert ist, sodass gleiche Werte nebeneinanderstehen. Gib die unterschiedlichen Werte von nums jeweils einmal und in der Reihenfolge zurück, in der sie vorkommen. Beispielsweise ergibt [2, 2, 5] den Wert [2, 5].

Funktion

removeDuplicates(nums: integer-array) → integer-array

numsinteger-array: die ganzen Zahlen, in nicht absteigender Reihenfolge sortiert
Gibt zurückinteger-array: die unterschiedlichen Werte von nums, in aufsteigender Reihenfolge

Einschränkungen

1 ≤ nums.length ≤ 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
nums ist in nicht absteigender Reihenfolge sortiert.

Beispiele

Eingabe: nums = [1, 1, 2, 3, 3, 3]
Ausgabe: [1, 2, 3]
Erklärung: 1 erscheint zweimal und 3 dreimal. Wenn man jeweils nur eines behält, erhält man [1, 2, 3].

Eingabe: nums = [-2, 0, 0, 5]
Ausgabe: [-2, 0, 5]
Erklärung: Nur 0 wird wiederholt. Negative Werte funktionieren genauso, daher lautet die Antwort [-2, 0, 5].

Eingabe: nums = [7, 7, 7]
Ausgabe: [7]
Erklärung: Jeder Wert ist 7, also bleibt nur noch eine 7 übrig.

+15 versteckte Tests beim Einreichen

Weiterführende Frage

Kannst du es mit zusätzlichem Speicheraufwand von O(1) erreichen, indem du nums direkt umschreibst, anstatt ein zweites Array zu erstellen?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Beim Entfernen von Duplikaten aus einem beliebigen Array musst du dir jeden Wert merken, den du bereits gesehen hast. Bei sortierter Eingabe ist das nicht nötig: Kopien eines Werts stehen nebeneinander, daher ist ein Wert genau dann neu, wenn er sich vom zuletzt übernommenen Wert unterscheidet. So wird die Aufgabe zu einem Durchlauf mit zwei Indizes und ohne zusätzlichen Speicher.

Bereits gesehene Werte in einer Hash-Menge speichern

Idee

Durchlaufe nums und führe eine Menge der Werte, die du bereits zur Antwort hinzugefügt hast. Wenn ein Wert nicht in der Menge ist, hänge ihn an die Antwort an und füge ihn der Menge hinzu; andernfalls überspringe ihn. Für [1, 1, 2, 3, 3, 3] wächst die Antwort auf [1], dann auf [1, 2], dann auf [1, 2, 3], und alle späteren Wiederholungen werden übersprungen.

Jeder Wert wird beim ersten Auftreten angehängt und danach nie wieder, und zwar in der Reihenfolge, in der du ihm begegnest, daher ist die Antwort korrekt. Dieser Ansatz nutzt nie die Tatsache, dass nums sortiert ist; er würde bei jedem Array funktionieren.

Mengenabfragen benötigen durchschnittlich O(1), daher benötigt der Durchlauf O(n) Zeit, aber sowohl die Menge als auch die Antwort können jeweils n Werte enthalten: O(n) zusätzlichen Speicherplatz. In C erledigt ein Flag-Array für die 2 × 10^4 + 1 möglichen Werte dieselbe Aufgabe, da es keine eingebaute Menge gibt.

Algorithmus

Erstelle eine leere Menge seen und eine leere Liste result.
Prüfe für jeden Wert in nums, ob er in seen enthalten ist.
Wenn nicht, füge ihn zu seen hinzu und hänge ihn an result an.
Gib result zurück.

def removeDuplicates(nums):
    seen = set()
    result = []
    for num in nums:
        if num not in seen:
            seen.add(num)
            result.append(num)
    return result

Kompaktieren an Ort und Stelle mit einem Schreibzeiger

Idee

Bei sortierter Eingabe bilden alle Kopien eines Werts einen zusammenhängenden Block, daher ist ein Wert genau dann neu, wenn er sich vom letzten gespeicherten Wert unterscheidet. Dafür braucht man einen Vergleich, keine Menge.

Verwende zwei Indizes. Der Leseindex i durchläuft jeden Wert. Der Schreibindex k markiert das Ende des behaltenen Teils: nums[0] bis nums[k-1] enthält immer die bisher gefundenen unterschiedlichen Werte. Beginne mit k = 1, da der erste Wert immer behalten wird. Wenn sich nums[i] von nums[k-1] unterscheidet, kopiere ihn nach nums[k] und erhöhe k.

Bei [1, 1, 2, 3, 3, 3]: i = 1 liest eine zweite 1, und es passiert nichts. i = 2 liest 2, das sich von nums[0] = 1 unterscheidet, also wird es an Index 1 geschrieben und k wird zu 2. i = 3 schreibt 3 an Index 2 und k wird zu 3. Die letzten beiden 3 stimmen mit nums[2] überein und werden übersprungen. Die ersten drei Plätze enthalten nun [1, 2, 3].

Der Schreibindex überholt den Leseindex nie, da k immer höchstens i ist; daher überschreibst du nie einen Wert, bevor du ihn gelesen hast. Ein Durchlauf benötigt O(n) Zeit, und abgesehen von den zurückgegebenen Werten verwendest du zwei Ganzzahlen: O(1) zusätzlichen Speicherplatz.

Algorithmus

Setze k = 1: nums[0] bleibt immer erhalten.
Durchlaufe i von 1 bis zum letzten Index.
Wenn nums[i] sich von nums[k-1] unterscheidet, setze nums[k] = nums[i] und erhöhe k um 1.
Gib die ersten k Werte von nums zurück.

def removeDuplicates(nums):
    # nums[0:k] holds the distinct values found so far, in order.
    k = 1
    for i in range(1, len(nums)):
        if nums[i] != nums[k - 1]:
            nums[k] = nums[i]
            k += 1
    return nums[:k]

Stolperfallen und Grenzfälle

Der Schreibzeiger ist kurz, und seine Fehler drehen sich darum, mit welchem Wert du vergleichst.

nums[i] mit nums[i+1] vergleichen, während i bis zum letzten Index läuft. Beim letzten Vergleich wird ein Element hinter dem Ende des Arrays gelesen.
k bei 0 beginnen lassen. Dann wird der erste Wert mit nums[-1] verglichen, was außerhalb des gültigen Bereichs liegt oder in Python das letzte Element ist.
Das ganze Array statt seiner ersten k Werte zurückgeben. Die übrigen Elemente enthalten noch alte Werte, sodass [1, 1, 2] als [1, 2, 2] zurückgegeben würde.
Die Antwort erstellen, indem du über ein Hash-Set iterierst. Ein Hash-Set behält in den meisten Sprachen keine Reihenfolge bei, sodass die Werte durcheinander ausgegeben werden können; füge stattdessen jeden Wert beim ersten Auftreten zu einer Liste hinzu.
In Lua und R beginnen Arrays bei 1. Der beibehaltene Teil reicht von nums[1] bis nums[k], und der Vergleich erfolgt mit nums[k], nicht mit nums[k-1].

Häufige Fragen4

Wie hoch ist die Zeitkomplexität beim Entfernen von Duplikaten aus einem sortierten Array?

Die Lösung mit dem Schreibzeiger liest jeden Wert einmal, sodass sie in O(n)-Zeit läuft. Neben den Werten, die sie zurückgibt, benötigt sie O(1) zusätzlichen Speicherplatz: zwei Indizes.

Warum muss das Array sortiert werden?

Beim Sortieren werden alle Vorkommen eines Werts in einem zusammenhängenden Abschnitt angeordnet. Daher ist ein Wert genau dann neu, wenn er sich vom zuletzt übernommenen Wert unterscheidet. In einem unsortierten Array kann ein Vorkommen weit entfernt vom ersten auftauchen, und du brauchst eine Hash-Menge, um dir alle bereits gesehenen Werte zu merken, was zusätzlichen Speicherplatz von O(n) kostet.

Wie entfernst du Duplikate direkt, ohne zusätzlichen Speicherplatz zu verwenden?

Führe neben dem Leseindex einen Schreibindex k. Die ersten k Plätze enthalten die bisher unterschiedlichen Werte. Wenn sich der gelesene Wert von nums[k-1] unterscheidet, kopiere ihn nach nums[k] und erhöhe k. Der Schreibindex überschreitet niemals den Leseindex, sodass nichts überschrieben wird, bevor es gelesen wurde.

Wie würdest du jeden Wert höchstens zweimal zulassen?

Vergleiche es mit dem Wert zwei Positionen zurück im beibehaltenen Teil statt mit dem Wert eine Position zurück: Kopiere nums[i], wenn k < 2 gilt oder wenn es sich von nums[k-2] unterscheidet. Wenn es gleich nums[k-2] ist, endet der beibehaltene Teil bereits mit zwei Kopien davon. Mit derselben Idee sind höchstens m Kopien möglich, indem du nums[k-m] verwendest.

Python

def removeDuplicates(nums):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

nums = [1, 1, 2, 3, 3, 3]

Erwartet

[1, 2, 3]