Duplikate direkt entfernen
Verwenden Sie ein Paar aus langsamem und schnellem Zeiger
Duplikate direkt entfernen ist eine kostenlose Competitive Programming Academy-Lektion auf CoddyKit. Dies ist Lektion 3 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Competitive Programming Academy-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.
Duplikate in-place entfernen
Gegeben ist ein sortiertes Array. Behalten Sie von jedem Wert eine Kopie, ohne ein zusätzliches Array zu verwenden. Die Bearbeitung an Ort und Stelle spart Speicher und ist eine klassische Interviewaufgabe. 🧹
Warum Sortieren hilft
Wenn das Array sortiert ist, steht jedes Duplikat direkt neben seinem Gegenstück. Sie müssen daher nur Nachbarn vergleichen, niemals das gesamte Array.
Zwei Rollen, zwei Zeiger
Verwenden Sie einen slow-Zeiger, der den zuletzt behaltenen Wert markiert, und einen fast-Zeiger, der vorausläuft und nach etwas Neuem sucht.
slow = 0
fast = 1Der slow-Zeiger schreibt
Betrachten Sie slow als Schreibposition: Alles an dieser Position oder davor ist bereits bereinigt und eindeutig.
Der fast-Zeiger liest
Der fast-Zeiger liest lediglich weiter. Er läuft voraus und meldet slow nur, wenn er einen noch nicht behaltenen Wert entdeckt.
Wiederholungen überspringen
Wenn a[fast] gleich a[slow] ist, handelt es sich um eine Wiederholung. Tun Sie nichts außer fast weiterzuschieben. Das Duplikat wird stillschweigend übersprungen.
for fast in range(1, n):
if a[fast] == a[slow]:
continueEtwas Neues gefunden
Wenn sich a[fast] unterscheidet, verschieben Sie slow nach vorn und kopieren den neuen Wert dorthin. Dadurch werden alte Duplikate mit neuen eindeutigen Daten überschrieben.
else:
slow += 1
a[slow] = a[fast]Die Antwort ist die Länge
Nach dem Durchlauf ist slow + 1 die Anzahl der eindeutigen Werte, die alle am Anfang des Arrays stehen.
return slow + 1Das Ende ignorieren
Alles, was hinter dem eindeutigen Präfix steht, sind übrig gebliebene Daten. Die Aufgabe berücksichtigt nur die ersten slow + 1 Elemente, lassen Sie den Rest daher unverändert.
An das leere Array denken
Ein leeres Array enthält keine eindeutigen Werte. Prüfen Sie n == 0 vor dem Start, damit Sie nicht hinter das Ende zugreifen.
if n == 0:
return 0Ein Durchlauf, kein zusätzlicher Speicher
Dieses Slow-Fast-Muster benötigt O(n) Zeit und O(1) zusätzlichen Speicher – genau das, was knappe Speichergrenzen verlangen.
Kurzer Check
Sie entfernen Duplikate in einem sortierten Array direkt an Ort und Stelle mit slow- und fast-Zeigern.
Zusammenfassung
In einem sortierten Array entfernt ein slow-fast-Paar Duplikate in einem O(n)-Durchlauf ohne zusätzlichen Speicher und gibt slow + 1 als Anzahl der eindeutigen Werte zurück. 🎉
Häufig gestellte Fragen
Ist die Lektion „Duplikate direkt entfernen“ kostenlos?
Ja — der vollständige Text von „Duplikate direkt entfernen“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Competitive Programming Academy-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Duplikate direkt entfernen“?
Verwenden Sie ein Paar aus langsamem und schnellem Zeiger Du übst Competitive Programming Academy mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um Competitive Programming Academy zu starten?
Keine Vorkenntnisse erforderlich. Competitive Programming Academy auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 3 von 4.
Wie lange dauert die Lektion „Duplikate direkt entfernen“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser Competitive Programming Academy-Lektion Code schreiben und ausführen?
Ja. Jede Competitive Programming Academy-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Zwei Zeiger in einem sortierten Array
- Ein Paar mit einer gegebenen Summe finden
- Duplikate direkt entfernen
- Zwei sortierte Sequenzen zusammenführen