Move Zeroes

Q: Jak przenieść zera na koniec, nie zmieniając kolejności pozostałych elementów?

Trzymaj indeks write wskazujący następne wolne miejsce z przodu i skanuj tablicę za pomocą drugiego indeksu. Każda znaleziona wartość różna od zera jest zamieniana z wartością w miejscu wskazywanym przez write , a indeks write przesuwa się o jedno miejsce w prawo. Wartości są umieszczane w kolejności, w jakiej je znajdujesz, więc ich względna kolejność nigdy się nie zmienia.

ŁatweDwa wskaźniki

+10

Otrzymujesz tablicę liczb całkowitych nums. Przenieś każde 0 na koniec tablicy, zachowując pozostałe wartości w ich dotychczasowej kolejności. Zwróć przestawioną tablicę o tej samej długości co nums.

Funkcja

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

numsinteger-array: tablica liczb całkowitych do przestawienia
Zwracainteger-array: tablica nums z wartościami niezerowymi na początku, w pierwotnej kolejności, a wszystkimi wartościami 0 na końcu

Ograniczenia

1 ≤ nums.length ≤ 5000
-10⁵ ≤ nums[i] ≤ 10⁵

Przykłady

Wejście: nums = [0, 4, 0, 7, 2]
Wyjście: [4, 7, 2, 0, 0]
Wyjaśnienie: Wartości, które nie są równe 0, to 4, 7 i 2, i pozostają w tej kolejności na początku. Dwa zera wypełniają dwa ostatnie miejsca.

+14 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Czy możesz przenieść wszystkie zera na początek, zachowując pozostałe wartości w tej samej kolejności, w jednym przebiegu i przy użyciu dodatkowej pamięci O(1)?

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Przeniesienie zer na koniec nie jest trudne. Trudność polega na zachowaniu pozostałych wartości w ich pierwotnej kolejności, co wyklucza zamienianie każdego 0 z ostatnim elementem. Podziel tablicę na początkową część zawierającą dotychczas znalezione wartości niezerowe oraz resztę. Jeden indeks odczytuje każdy element, drugi wskazuje miejsce dla następnej wartości niezerowej, a jedno przejście kończy zadanie w miejscu.

Skopiuj wartości różne od zera

Intuicja

Utwórz nową tablicę. Przejdź przez nums i skopiuj każdą wartość, która nie jest równa 0, w kolejności, w jakiej ją napotkasz. Następnie dodaj zera, aż nowa tablica będzie miała taką samą długość jak nums. Liczba dodanych zer jest równa liczbie pominiętych elementów.

Dla [0, 4, 0, 7, 2] etap kopiowania daje [4, 7, 2], a dwa zera tworzą [4, 7, 2, 0, 0]. Kolejność jest poprawna, ponieważ kopiujesz wartości w takiej kolejności, w jakiej je odczytujesz.

Każdy element jest odczytywany raz i zapisywany raz, więc czas działania wynosi O(n). Druga tablica wymaga O(n) pamięci, czego pozwala uniknąć następne podejście.

Algorytm

Utwórz pustą tablicę wynikową.
Dla każdej wartości w nums dodaj ją do wyniku, jeśli nie jest równa 0.
Dodawaj zera, aż wynik będzie zawierał tyle samo elementów co nums.
Zwróć wynik.

def moveZeroes(nums):
    result = [x for x in nums if x != 0]
    result += [0] * (len(nums) - len(result))
    return result

Dwa wskaźniki, zamiana na miejscu

Intuicja

Użyj dwóch indeksów. read odwiedza każdy element od lewej do prawej. write wskazuje miejsce, do którego należy wstawić następną niezerową wartość. Po każdym kroku zachodzą dwa fakty: wszystko przed write to widziane do tej pory wartości niezerowe, w ich pierwotnej kolejności, a wszystko od write do read to 0.

Gdy nums[read] nie jest równe 0, zamień je z nums[write] i przesuń write o jeden krok w prawo. Wartość, która trafia na pozycję read, to 0 ze strefy zer albo ta sama wartość, gdy oba indeksy są równe. Wartości niezerowe przeskakują tylko nad zerami, nigdy nad sobą nawzajem, więc ich kolejność zostaje zachowana.

Dla [0, 4, 0, 7, 2]: 4 na indeksie 1 zamienia się miejscami z elementem na indeksie 0, dając [4, 0, 0, 7, 2]. 7 na indeksie 3 zamienia się miejscami z elementem na indeksie 1, dając [4, 7, 0, 0, 2]. 2 na indeksie 4 zamienia się miejscami z elementem na indeksie 2, dając [4, 7, 2, 0, 0]. Jeden przebieg i bez drugiej tablicy: czas O(n) i pamięć O(1).

Algorytm

Ustaw write na 0.
Przesuń read od pierwszego indeksu do ostatniego.
Jeśli nums[read] nie jest równe 0, zamień nums[read] miejscami z nums[write], a następnie zwiększ write o 1.
Zwróć nums.

def moveZeroes(nums):
    write = 0  # nums[:write] holds the non-zero values found so far, in order
    for read in range(len(nums)):
        if nums[read] != 0:
            nums[write], nums[read] = nums[read], nums[write]
            write += 1
    return nums

Pułapki i przypadki brzegowe

Typowe błędy albo zmieniają kolejność pozostałych wartości, albo pomijają elementy.

Zamiana każdego 0 z ostatnim elementem przesuwa zera, ale miesza kolejność pozostałych wartości: [0, 4, 7] staje się [7, 4, 0].
Usuwanie zer z tablicy podczas przechodzenia po niej za pomocą indeksu powoduje pomijanie elementów. W [0, 0, 5] usunięcie elementu o indeksie 0 przesuwa drugie 0 na indeks 0, a pętla przechodzi do indeksu 1. Każde usunięcie przesuwa również resztę tablicy, przez co pętla ma złożoność O(n²).
Sprawdzaj x != 0, a nie x > 0. Wartości ujemne nie są zerami: [-1, 0, -2] musi zmienić się w [-1, -2, 0], ale wersja kopiująca z warunkiem x > 0 zwraca [0, 0, 0].
Tablica bez zer lub zawierająca tylko zera musi pozostać bez zmian. W wersji z zamianą read i write są równe aż do napotkania pierwszego 0, więc te zamiany niczego nie zmieniają.
W Lua i R tablice zaczynają się od 1, więc write również zaczyna się od 1.

Najczęstsze pytania4

Jaka jest złożoność czasowa algorytmu Move Zeroes?

O(n). Oba podejścia odczytują każdy element raz. Skopiowanie wartości niezerowych do nowej tablicy wymaga dodatkowej pamięci O(n), natomiast zamiana za pomocą dwóch wskaźników odbywa się w obrębie tablicy i wymaga dodatkowej pamięci O(1).

Jak przenieść zera na koniec, nie zmieniając kolejności pozostałych elementów?

Trzymaj indeks write wskazujący następne wolne miejsce z przodu i skanuj tablicę za pomocą drugiego indeksu. Każda znaleziona wartość różna od zera jest zamieniana z wartością w miejscu wskazywanym przez write, a indeks write przesuwa się o jedno miejsce w prawo. Wartości są umieszczane w kolejności, w jakiej je znajdujesz, więc ich względna kolejność nigdy się nie zmienia.

Czy zadanie „Przenieś zera” można wykonać, wykonując mniej zapisów?

Tak. Zamiast zamieniać wartości miejscami, skopiuj każdą niezerową wartość do nums[write], a po przejrzeniu tablicy wypełnij każde miejsce od write do końca wartością 0. Dzięki temu każda pozycja jest zapisywana najwyżej raz. Możesz też pominąć zamianę, gdy read jest równe write, ponieważ wartość zostałaby zapisana z powrotem w tym samym miejscu.

Dlaczego Move Zeroes to problem z dwoma wskaźnikami?

Jeden wskaźnik odczytuje każdy element, a drugi oznacza koniec gotowej przedniej części. Oba przesuwają się tylko do przodu, więc razem wykonują jedno przejście. Ten sam wzorzec odczytu i zapisu usuwa duplikaty z posortowanej tablicy lub filtruje dowolną wartość z tablicy w miejscu.

Python

def moveZeroes(nums):
    # Napisz kod tutaj

Przypadki testowe

Przypadek 1

Przypadek 2

Przypadek 3

Wejście

nums = [0, 4, 0, 7, 2]

Oczekiwane

[4, 7, 2, 0, 0]