Pythonで配列内のゼロを複製するアルゴリズムを解説

問題の概要

固定長の整数型配列が与えられたとき、配列内に出現するゼロ（0）をそれぞれ2つに複製し、それに応じて残りの要素を右側へずらすという問題を考えてみましょう。

ただし、元の配列の長さを超える部分には要素を書き込まない点に注意が必要です。つまり、右にずらされたことで範囲外となった要素は単純に切り捨てられます。

例えば、配列が [1,0,2,3,0,4,5,0] の場合、処理後は [1,0,0,2,3,0,0,4] となります。

解き方のアプローチ

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

• 元の配列 arr を別の配列 arr2 にコピーし、インデックス i と j をそれぞれ 0 で初期化します。
• i が arr のサイズ未満である間、以下を繰り返します。
  • arr2[j] がゼロの場合：
    • arr[i] に 0 を代入し、i を1増やします。
    • その後も i が配列のサイズ未満であれば、arr[i] にもう1つの 0 を代入します（これが「複製」の処理です）。
  • ゼロ以外の場合：そのまま arr[i] に arr2[j] の値をコピーします。
  • 最後に i と j をそれぞれ1増やして次へ進みます。

ポイントは、元の配列を直接書き換えるとまだ読んでいない要素が上書きされてしまうため、コピーした配列を読み取り用（arr2）、元の配列を書き込み用（arr）として使うことです。これにより、ゼロを複製しながら残りの要素を正しく右へシフトできます。

実装例

理解を深めるために、実際のPythonコードを見てみましょう。

class Solution(object):
    def duplicateZeros(self, arr):
        arr2 = [i for i in arr]
        i = 0
        j = 0
        while i < len(arr):
            if not arr2[j]:
                arr[i] = 0
                i += 1
                if i < len(arr):
                    arr[i] = 0
            else:
                arr[i] = arr2[j]
            j += 1
            i += 1
        return arr

ob1 = Solution()
print(ob1.duplicateZeros([1,0,2,3,0,4,5,0]))

入力

[1,0,2,3,0,4,5,0]

出力

[1,0,0,2,3,0,0,4]

計算量について

このアルゴリズムの時間計算量は O(n)、空間計算量もコピー用の配列を作るため O(n) となります。なお、追加の配列を使わないO(1) の空間計算量で実現する二重ループ（逆方向走査）の手法も存在します。まずゼロの総数を数えて最終的な長さを求め、配列を後ろから埋めていくことで、余分なメモリを削減できます。面接などではこの最適化について言及できると評価が高まるでしょう。