Pythonでリスト内のゼロを末尾へ移動する方法【インプレース処理・O(1)メモリ】

問題概要

数値のリスト nums が与えられたとき、リストをインプレース（元のリストを直接書き換える形）で更新し、すべてのゼロをリストの末尾へ移動することを考えます。その際、ゼロ以外の要素の相対的な順序は変更してはいけません。また、追加で使用できるメモリ領域は O(1) という制約があります。

たとえば、入力が [2,0,1,4,0,5,6,4,0,1,7] の場合、出力は [2, 1, 4, 5, 6, 4, 1, 7, 0, 0, 0] となります。

アルゴリズムの手順

この問題は、2つのポインタ（インデックス）を使うテクニックで効率的に解くことができます。手順は以下のとおりです。

• L のサイズが 0 の場合は、空のリストを返します。
• k := 0 と初期化します。k は「ゼロ以外の要素を書き込む位置」を表します。
• i を 0 から L のサイズ - 1 まで順に処理します。
  • L[i] が 0 以外の場合、L[k] := L[i] として値を前方に詰め、k を 1 増やします。
• 次に、j を k から L のサイズ - 1 まで順に処理します。
  • L[j] := 0 として、残りの部分をゼロで埋めます。
• 最後に L を返します。

この方法では、リスト全体を2回走査するだけで済み、余分なリストを作成しないため、追加メモリは O(1) で抑えられます。

実装例

以下のコードで具体的な実装を確認できます。

class Solution:
    def solve(self, L):
        if len(L) == 0:
            return []
        k = 0
        for i in range(len(L)):
            if L[i] != 0:
                L[k] = L[i]
                k += 1
        for j in range(k, len(L)):
            L[j] = 0
        return L

ob = Solution()
L = [2, 0, 1, 4, 0, 5, 6, 4, 0, 1, 7]
print(ob.solve(L))

入力

[2,0,1,4,0,5,6,4,0,1,7]

出力

[2, 1, 4, 5, 6, 4, 1, 7, 0, 0, 0]

計算量

• 時間計算量：O(n) — リストを2回走査するだけです。
• 空間計算量：O(1) — 追加のデータ構造を使用しません。

補足：別のアプローチとの比較

Python では list.remove(0) と list.append(0) を組み合わせる方法も考えられますが、remove() は要素を先頭から探すため O(n) の操作となり、ゼロが多いリストでは非効率です。本記事で紹介した2ポインタ方式は、どのような入力に対しても安定して O(n) で動作するため、実務やコーディング面接でも推奨される手法です。