Szybki Python – move zeros

Rozwiązujemy (w optymalnej wersji) znany problem move zeros, czyli przesuwania zer w tablicy na jej koniec przy zachowaniu odpowiedniej kolejności liczb, które nie są zerami. Robimy to w języku Python.

Zacznijmy od jakiejś listy zawierającej zera i inne liczby:

arr = [1,0,2,0,3]

Okej, piszemy szkielet funkcji:

arr = [1,0,2,0,3]
def moveZeroes(nums):
    for num in nums:
        print(num)
moveZeroes(arr)
# 1
# 0
# 2
# 0
# 3

Jak widać za pomocą for przechodzi nam po elementach i pod num mamy aktualną liczbę w danej iteracji.

Teraz dodajmy drugi wskaźnik, który idzie od 0, ale przesuwa się o 1 tylko wtedy, gdy num (liczba w danej iteracji) nie jest zerem:

arr = [1,0,2,0,3]
def moveZeroes(nums):
    j = 0
    for num in nums:
        print(num)
        if num != 0:
            j +=1
    else:
        print("----------")
        print(j)
moveZeroes(arr)
# 1
# 0
# 2
# 0
# 3
# ----------
# 3

Konstrukcja for-else może wydawać się nam cokolwiek egzotyczna, ale nie na tym powinniśmy się skupić. Za każdym razem, gdy num nie było zerem, było przesuwane o jeden w prawo.

Num zatrzymało się na indeksie 3. Od indeksu 3 aż do końca powinny być same zera. Przed indeksem 3 zaś liczby powinny być pozamieniane.

To jest – ilekroć num nie jest zerem, zamieniasz miejsce o indeksie j (pozycja ostatniego zera) na num i zwiększasz j, które na końcu i tak stanie w miejscu, gdzie będą potrzebne kolejne zera.

arr = [1,0,2,0,3]
def moveZeroes(nums):
    j = 0
    for num in nums:
        if num != 0:
            nums[j] = num
            j +=1
    else:
        print(j)
moveZeroes(arr)
# 3
print(arr)
#[1, 2, 3, 0, 3]

Wskaźnik j zawsze będzie wskazywać miejsce ostatniego zera, zaś num zawsze aktualną liczbę. I jeżeli ta liczba nie jest zerem, to zamieniamy miejsce zajmowane przez j na nią i przesuwamy j.

Koniec końców liczby nie-zerowe są już na właściwym miejscu, mamy też indeks miejsca, od którego chcemy mieć zera aż do końca.

Wystarczy dodać jedną pętlę i usunąć już zbędny debug:

arr = [1,0,2,0,3]
def moveZeroes(nums):
    j = 0
    for num in nums:
        if num != 0:
            nums[j] = num
            j +=1
    for x in range(j, len(nums)):
        nums[x] = 0
        
moveZeroes(arr)
print(arr)
# [1, 2, 3, 0, 0]

Przypominam, że jedna pętla albo dwie, albo i dziesięć wykonywanych sekwencyjnie, bez zagnieżdżenia, to złożoność O(n).

W przypadku zagnieżdżenia pętli w pętli mamy O(n2), O(n3) przy potrójnym zagnieżdżeniu i tak dalej.

Nie należy się zatem bać w rozwiązywaniu algorytmicznych zadań wykonania kolejnej pętli. To się może wydawać niewłaściwe, zbyt złożone, możemy myśleć, że gdzieś polegliśmy z naszą logiką, ale tak nie jest.

Jeżeli użyliśmy nawet jednej pętli, to już mamy złożoność O(n). To też nie jest żaden grzech, są problemy, których nie da się rozwiązać mniejszą złożonością, są takie, dla których O(n) to złożoność jak najbardziej właściwa.

Natomiast dodawanie kolejnych pętli nie zwiększa nam złożoności. Może się nam tylko wydawać, że skoro robimy kolejną pętlę, to coś musimy robić źle. Wcale tak nie jest.