リストのお尻に0を移動させる問題

問題

今日はMove all zeroes to end of arrayの問題にチャレンジする。この問題は、ランダムな値をもつリストの要素の順番を並び替える問題で、0以外を前に移動させ、0は後ろに移動させる問題。

Input : [1, 9, 8, 4, 0, 0, 2, 7, 0, 6, 0, 9]
Output: [1, 9, 8, 4, 2, 7, 6, 9, 0, 0, 0, 0]

実装

問題を2つに分けて考えるとわかりやすいとのこと。つまり、「0以外の要素を前に移動させる部分」と「0で埋める部分」の2つ。まずは「0以外の要素を前に移動させる部分」については、インデックスiとcountを使ってiでリストをループさせて値を確認し、インデックスcountで値を移動させる場所を決める。この部分がおわると、countのインデックス以降は、「0で埋める部分」となるので、そこに0を入れていけば、問題を解決できる。

from typing import List


def pushZerosToEnd(numbers: List[int]) -> List[int]:
    len_numbers = len(numbers)
    count = 0

    for i in range(len_numbers):
        if numbers[i] != 0:
            numbers[count] = numbers[i]
            count += 1

    while count < len_numbers:
        numbers[count] = 0
        count += 1

if __name__ == '__main__':
    numbers = [1, 9, 8, 4, 0, 0, 2, 7, 0, 6, 0, 9]
    print(numbers)
    pushZerosToEnd(numbers)
    print(numbers)

[1, 9, 8, 4, 0, 0, 2, 7, 0, 6, 0, 9]
[1, 9, 8, 4, 2, 7, 6, 9, 0, 0, 0, 0]

もっと短く書くこともできる。

from typing import List


def pushZerosToEnd2(numbers: List[int]) -> List[int]:
    len_numbers = len(numbers)
    count = 0

    for i in range(0, len_numbers):
        if (numbers[i] != 0):
            numbers[count], numbers[i] = numbers[i], numbers[count]
            count += 1

if __name__ == '__main__':
    numbers = [1, 9, 8, 4, 0, 0, 2, 7, 0, 6, 0, 9]
    print(numbers)
    pushZerosToEnd2(numbers)
    print(numbers)

[1, 9, 8, 4, 0, 0, 2, 7, 0, 6, 0, 9]
[1, 9, 8, 4, 2, 7, 6, 9, 0, 0, 0, 0]