Usuwanie duplikatów w miejscu
Używanie pary wolnego i szybkiego wskaźnika
Usuwanie duplikatów w miejscu to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 3 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Coding Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Usuwanie duplikatów w miejscu
Mając posortowaną tablicę, należy pozostawić po jednej kopii każdej wartości bez używania dodatkowej tablicy. Operowanie w miejscu oszczędza pamięć i jest klasycznym zadaniem rekrutacyjnym. 🧹
Dlaczego sortowanie pomaga
Gdy tablica jest posortowana, każdy duplikat znajduje się bezpośrednio obok swojego odpowiednika. Wystarczy więc porównywać sąsiadów, a nie całą tablicę.
Dwie role, dwa wskaźniki
Należy użyć wskaźnika slow, który wskazuje ostatnią zachowaną wartość, oraz wskaźnika fast, który przegląda kolejne elementy w poszukiwaniu czegoś nowego.
slow = 0
fast = 1Wskaźnik slow zapisuje
Wskaźnik slow należy traktować jako pozycję zapisu: wszystko na tej pozycji i przed nią zostało już oczyszczone i jest unikatowe.
Wskaźnik fast odczytuje
Wskaźnik fast tylko odczytuje kolejne elementy. Pędzi do przodu i sygnalizuje wskaźnikowi slow znalezienie wartości, której jeszcze nie zachowano.
Pomijanie powtórzeń
Jeśli a[fast] jest równe a[slow], jest to powtórzenie, więc nie należy nic robić poza przesunięciem fast. Duplikat zostaje po prostu pominięty.
for fast in range(1, n):
if a[fast] == a[slow]:
continueZnaleziono coś nowego
Gdy a[fast] różni się od a[slow], należy przesunąć slow do przodu i skopiować tam nową wartość. W ten sposób stare duplikaty zostają zastąpione nowymi, unikatowymi danymi.
else:
slow += 1
a[slow] = a[fast]Odpowiedzią jest długość
Po zakończeniu przejścia slow + 1 oznacza liczbę unikatowych wartości zgromadzonych na początku tablicy.
return slow + 1Należy zignorować końcówkę
Wszystko, co znajduje się za unikatowym prefiksem, jest pozostałością bez znaczenia. Problem dotyczy tylko pierwszych slow + 1 elementów, więc końcówkę można pozostawić bez zmian.
Należy pamiętać o pustej tablicy
Pusta tablica zawiera zero unikatowych wartości. Przed rozpoczęciem należy sprawdzić n == 0, aby nie odczytać elementu poza końcem tablicy.
if n == 0:
return 0Jedno przejście, bez dodatkowej pamięci
Ten schemat slow-fast działa w czasie O(n) i używa O(1) dodatkowej pamięci, dokładnie tak, jak wymagają tego ścisłe limity pamięci.
Szybkie sprawdzenie
Usuwają Państwo duplikaty w miejscu z posortowanej tablicy za pomocą wolnego i szybkiego wskaźnika.
Podsumowanie
W posortowanej tablicy para wskaźników slow-fast usuwa duplikaty w jednym przejściu O(n), bez dodatkowej pamięci, zwracając slow + 1 jako liczbę unikatowych wartości. 🎉
Często zadawane pytania
Czy lekcja „Usuwanie duplikatów w miejscu” jest bezpłatna?
Tak — pełny tekst „Usuwanie duplikatów w miejscu” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Usuwanie duplikatów w miejscu”?
Używanie pary wolnego i szybkiego wskaźnika Ćwiczysz Coding Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć Coding Interview Prep?
Nie wymagamy żadnego doświadczenia. Coding Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 3 z 4.
Ile czasu zajmuje lekcja „Usuwanie duplikatów w miejscu”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji Coding Interview Prep?
Tak. Każda lekcja Coding Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Dwa wskaźniki w posortowanej tablicy
- Znajdowanie pary o zadanej sumie
- Usuwanie duplikatów w miejscu
- Scalanie dwóch posortowanych sekwencji