Remove Duplicates from Sorted Array

Q: Jak usunąć duplikaty w miejscu, bez dodatkowej pamięci?

Umieść indeks zapisu k obok indeksu odczytu. Pierwsze k miejsc zawierają dotychczasowe różne wartości. Gdy odczytana wartość różni się od nums[k-1] , skopiuj ją do nums[k] i zwiększ k . Indeks zapisu nigdy nie wyprzedza indeksu odczytu, więc nic nie zostaje nadpisane, zanim zostanie odczytane.

ŁatweDwa wskaźniki

+10

Otrzymujesz tablicę liczb całkowitych nums posortowaną w kolejności niemalejącej, więc równe wartości znajdują się obok siebie. Zwróć różne wartości z nums, każdą tylko raz, w kolejności, w jakiej występują. Na przykład [2, 2, 5] daje [2, 5].

Funkcja

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

numsinteger-array: liczby całkowite, posortowane w kolejności niemalejącej
Zwracainteger-array: różne wartości nums, w kolejności rosnącej

Ograniczenia

1 ≤ nums.length ≤ 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
nums jest posortowane w kolejności niemalejącej.

Przykłady

Wejście: nums = [1, 1, 2, 3, 3, 3]
Wyjście: [1, 2, 3]
Wyjaśnienie: 1 występuje dwa razy, a 3 trzy razy. Pozostawiając po jednym z każdego, otrzymujemy [1, 2, 3].

Wejście: nums = [-2, 0, 0, 5]
Wyjście: [-2, 0, 5]
Wyjaśnienie: Powtarza się tylko 0. Wartości ujemne działają tak samo, więc odpowiedzią jest [-2, 0, 5].

Wejście: nums = [7, 7, 7]
Wyjście: [7]
Wyjaśnienie: Każda wartość to 7, więc została już tylko jedna 7.

+15 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Czy potrafisz zrobić to przy użyciu dodatkowej pamięci O(1), modyfikując nums w miejscu zamiast tworzyć drugą tablicę?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Usuwanie duplikatów z dowolnej tablicy wymaga zapamiętywania każdej napotkanej wartości. Posortowane dane wejściowe eliminują tę potrzebę: kopie danej wartości sąsiadują ze sobą, więc wartość jest nowa dokładnie wtedy, gdy różni się od ostatniej zachowanej. Dzięki temu zadanie można wykonać w jednym przebiegu za pomocą dwóch indeksów i bez dodatkowej pamięci.

Zapamiętuj widziane wartości w zbiorze haszującym

Intuicja

Przejdź przez nums i przechowuj zbiór wartości, które zostały już dodane do odpowiedzi. Jeśli danej wartości nie ma w zbiorze, dopisz ją do odpowiedzi i dodaj do zbioru; jeśli jest, pomiń ją. Dla [1, 1, 2, 3, 3, 3] odpowiedź rośnie do [1], potem [1, 2], a następnie [1, 2, 3], a każde kolejne wystąpienie jest pomijane.

Każda wartość jest dopisywana przy pierwszym wystąpieniu i nigdy więcej, w kolejności, w jakiej ją napotykasz, więc odpowiedź jest poprawna. To podejście nigdy nie wykorzystuje faktu, że nums jest posortowana; zadziałałoby dla dowolnej tablicy.

Wyszukiwanie w zbiorze zajmuje średnio O(1), więc jedno przejście zajmuje O(n) czasu, ale zarówno zbiór, jak i odpowiedź mogą zawierać po n wartości: O(n) dodatkowej pamięci. W C, gdzie nie ma wbudowanego zbioru, tablica znaczników dla 2 × 10^4 + 1 możliwych wartości spełnia to samo zadanie.

Algorytm

Utwórz pusty zbiór seen i pustą listę result.
Dla każdej wartości w nums sprawdź, czy znajduje się w seen.
Jeśli jej tam nie ma, dodaj ją do seen i dołącz do result.
Zwróć result.

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

Kompaktowanie w miejscu za pomocą wskaźnika zapisu

Intuicja

W posortowanych danych wejściowych wszystkie kopie danej wartości tworzą jeden ciąg, więc wartość jest nowa dokładnie wtedy, gdy różni się od ostatniej zachowanej wartości. Wymaga to jednego porównania, a nie zbioru.

Użyj dwóch indeksów. Indeks odczytu i odwiedza każdą wartość. Indeks zapisu k wyznacza koniec zachowanej części: od nums[0] do nums[k-1] znajdują się zawsze wszystkie dotąd znalezione różne wartości. Zacznij od k = 1, ponieważ pierwsza wartość jest zawsze zachowywana. Gdy nums[i] różni się od nums[k-1], skopiuj ją do nums[k] i zwiększ k.

Dla [1, 1, 2, 3, 3, 3]: i = 1 odczytuje drugą 1 i nic się nie dzieje. i = 2 odczytuje 2, która różni się od nums[0] = 1, więc zostaje zapisana pod indeksem 1, a k przyjmuje wartość 2. i = 3 zapisuje 3 pod indeksem 2, a k przyjmuje wartość 3. Dwie ostatnie wartości 3 są równe nums[2] i zostają pominięte. Pierwsze trzy pozycje zawierają teraz [1, 2, 3].

Zapis nigdy nie wyprzedza odczytu, ponieważ k jest zawsze mniejsze lub równe i, więc nigdy nie nadpisujesz wartości, zanim ją odczytasz. Jedno przejście zajmuje O(n) czasu, a poza zwracanymi wartościami używasz dwóch liczb całkowitych: dodatkowa przestrzeń wynosi O(1).

Algorytm

Ustaw k = 1: nums[0] jest zawsze zachowywane.
Przejdź pętlą po i od 1 do ostatniego indeksu.
Jeśli nums[i] różni się od nums[k-1], ustaw nums[k] = nums[i] i zwiększ k o 1.
Zwróć pierwsze k wartości z nums.

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]

Pułapki i przypadki brzegowe

Wskaźnik zapisu jest krótki, a błędy dotyczą tego, z jaką wartością go porównujesz.

Porównywanie nums[i] z nums[i+1], gdy i dochodzi do ostatniego indeksu. Ostatnie porównanie odczytuje element znajdujący się poza końcem tablicy.
Rozpoczynanie od k równego 0. Wtedy pierwsza wartość jest porównywana z nums[-1], który znajduje się poza zakresem albo w Pythonie oznacza ostatni element.
Zwracanie całej tablicy zamiast jej pierwszych k wartości. Pozostała część nadal zawiera stare wartości, więc [1, 1, 2] zostałoby zwrócone jako [1, 2, 2].
Budowanie odpowiedzi przez iterowanie po zbiorze haszującym. W większości języków zbiory haszujące nie zachowują kolejności, więc wartości mogą pojawić się w przypadkowej kolejności; zamiast tego dodawaj każdą wartość do listy, gdy napotkasz ją po raz pierwszy.
W Lua i R tablice zaczynają się od 1. Zachowana część obejmuje elementy od nums[1] do nums[k], a porównanie jest wykonywane z nums[k], nie z nums[k-1].

Najczęstsze pytania4

Jaka jest złożoność czasowa problemu „Usuwanie duplikatów z posortowanej tablicy”?

Rozwiązanie z wskaźnikiem zapisu odczytuje każdą wartość raz, więc działa w czasie O(n). Oprócz zwracanych wartości używa O(1) dodatkowej pamięci: dwóch indeksów.

Dlaczego tablica musi być posortowana?

Sortowanie umieszcza wszystkie kopie danej wartości w jednym ciągu, więc wartość jest nowa dokładnie wtedy, gdy różni się od ostatniej zachowanej wartości. W nieposortowanej tablicy kopia może pojawić się daleko od pierwszej, a do zapamiętania każdej napotkanej wartości potrzebujesz zbioru haszującego, co wymaga dodatkowej pamięci O(n).

Jak usunąć duplikaty w miejscu, bez dodatkowej pamięci?

Umieść indeks zapisu k obok indeksu odczytu. Pierwsze k miejsc zawierają dotychczasowe różne wartości. Gdy odczytana wartość różni się od nums[k-1], skopiuj ją do nums[k] i zwiększ k. Indeks zapisu nigdy nie wyprzedza indeksu odczytu, więc nic nie zostaje nadpisane, zanim zostanie odczytane.

Jak zezwolić na wystąpienie każdej wartości najwyżej dwa razy?

Porównaj z wartością sprzed dwóch miejsc w zachowanej części, zamiast z tą sprzed jednego miejsca: skopiuj nums[i], gdy k < 2 lub gdy różni się od nums[k-2]. Jeśli jest równa nums[k-2], zachowana część kończy się już dwiema jej kopiami. Ta sama idea pozwala zachować co najwyżej m kopii za pomocą nums[k-m].

Python

def removeDuplicates(nums):
    # Wpisz kod tutaj

Przypadki testowe

Przypadek 1

Przypadek 2

Przypadek 3

Wejście

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

Oczekiwane

[1, 2, 3]