Pythonで配列内のゼロを右端に移動するアルゴリズム

数値を格納する配列を考えてみましょう。この配列には、ゼロ以外の値とゼロの値が混在しています。ここでの課題は、他の数値の相対的な順序を変えずに、すべてのゼロを配列の右端（末尾）へ移動させることです。

例えば、配列が [0, 1, 5, 0, 3, 8, 0, 0, 9] の場合、処理後の最終的な配列は [1, 5, 3, 8, 9, 0, 0, 0, 0] となります。

解決手順

この問題は、次の手順で解くことができます。

• 挿入位置を記録するためのインデックス index を 0 で初期化します。
• i = 0 から配列 A の長さまで繰り返します。
  • A[i] != 0 の場合：
    • A[index] := A[i] と代入します。
    • index := index + 1 として挿入位置を進めます。
• i = index から配列 A の長さまで繰り返し、A[i] = 0 を代入して残りをゼロで埋めます。

実装例

以下の実装例を見て、動作をより深く理解しましょう。

class Solution(object):
    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        insert_index = 0
        for i in range(len(nums)):
            if nums[i] != 0:
                nums[insert_index] = nums[i]
                insert_index += 1
        for i in range(insert_index, len(nums)):
            nums[i] = 0

nums = [0, 1, 5, 0, 3, 8, 0, 0, 9]
ob1 = Solution()
ob1.moveZeroes(nums)
print(nums)

入力

nums = [0, 1, 5, 0, 3, 8, 0, 0, 9]

出力

[1, 5, 3, 8, 9, 0, 0, 0, 0]

アルゴリズムのポイント

この手法は、いわゆる二重ポインタ（Two Pointers）と呼ばれるテクニックの一種です。まず最初のループで、ゼロ以外の要素だけを配列の前方へ順番に詰めていきます。その後、2つ目のループで残りの位置にゼロを埋めることで、元の順序を保ったままゼロを右端へ集めることができます。

計算量は O(n)、空間計算量は O(1) です。配列をその場（in-place）で直接書き換えるため、追加のメモリも不要であり、非常に効率的なアプローチと言えます。