Pythonで行列をインプレースでゼロ化するアルゴリズム

ある行列が与えられたとき、その中に0 の要素が1つでも存在すれば、その要素を含む行と列全体をすべて 0 に置き換えます。この変換はインプレース（追加の行列を使用せず、元の配列上で直接書き換える）方式で行う必要があります。

問題の例

たとえば、次のような3×3の行列があったとします。

この場合の出力は以下のようになります。

左上（0行目・0列目の交点）に 0 があるため、0行目と0列目がすべて 0 に変わっていますね。

アルゴリズムの手順

この問題では、行列の1行目と1列目をフラグ（マーカー）として活用することで、追加メモリ O(1) で解くことができます。手順は以下の通りです。

1. 行数を n、列数を m とし、flag := false で初期化します。
2. mat[0, 0] = 0 の場合は、flag := true に設定します。
3. row := false、col := false と初期化します。
4. i を 1 〜 n-1 までループし、mat[i, 0] = 0 なら col := true にしてループを抜けます。
5. i を 1 〜 m-1 までループし、mat[0, i] = 0 なら row := true にしてループを抜けます。
6. i を 1 〜 n-1、j を 1 〜 m-1 まで二重ループし、mat[i, j] = 0 なら mat[i, 0] = 0 および mat[0, j] = 0 を設定します（マーカーの記録）。
7. 同じ範囲で再び二重ループし、mat[i, 0] = 0 または mat[0, j] = 0 なら mat[i, j] = 0 にします（マーカーに基づくゼロ化）。
8. flag が立っている場合（左上が元々 0 だった場合）は、0列目と0行目をすべて 0 にします。
9. そうでない場合は、col が立っていれば 0列目を、row が立っていれば 0行目をそれぞれ 0 にします。

実装例

それでは、実際のPythonコードを見てみましょう。

class Solution(object):
   def setZeroes(self, matrix):
      n = len(matrix)
      m = len(matrix[0])
      flag = False
      if matrix[0][0] == 0:
         flag = True
         row = False
         column = False
      for i in range(1,n):
         if matrix[i][0] == 0:
            column = True
            break
      for i in range(1,m):
         if matrix[0][i] == 0:
            row = True
            break
      for i in range(1,n):
         for j in range(1,m):
            if matrix[i][j] == 0:
               matrix[0][j] = 0
               matrix[i][0]=0
      for i in range(1,n):
         for j in range(1,m):
            if not matrix[i][0] or not matrix[0][j]:
               matrix[i][j] = 0
      if flag:
         for i in range(n):
            matrix[i][0] = 0
         for i in range(m):
            matrix[0][i]=0
      else:
         if column:
            for i in range(n):
               matrix[i][0]=0
         if row:
            for i in range(m):
               matrix[0][i]=0
      return matrix
ob1 = Solution()
print(ob1.setZeroes([[1,0,1],[1,1,1],[1,1,1]]))

入力

[[1,0,1],[1,1,1],[1,1,1]]

出力

[[0, 0, 0], [1, 0, 1], [1, 0, 1]]

計算量について

• 時間計算量： O(n × m) — 行列の全要素を最大2回走査します。
• 空間計算量： O(1) — フラグ用の変数のみを使用し、追加のデータ構造は不要です。

このように、1行目と1列目をマーカーとして再利用するテクニックを使えば、余分なメモリを消費せずに効率的にゼロ化処理を実現できます。