Set Matrix Zeroes
入力は整数のm × nグリッドで、行ごとに与えられます。そのため、matrix[i][j]は行i、列jにあります。グリッド内で0がある箇所では、その行全体と列全体を0にしてください。最初から存在する0だけを対象とします。0に変更したセルによって、その行や列がクリアされることはありません。グリッドをその場で変更してもかまいません。変更したグリッドを返してください。
関数
- matrixinteger-2d-array
- 整数のグリッド。各行に1つの内側リスト
- 戻り値integer-2d-array
- 0を含んでいたすべての行と列を0にした行列
制約
m == matrix.lengthおよびn == matrix[i].length1 ≤ m, n ≤ 1000andm × n ≤ 5000- すべての
m行にはn個の値が含まれています。 -1000 ≤ matrix[i][j] ≤ 1000
例
- 入力
- matrix = [[3, 8, 1], [5, 0, 7], [2, 6, 4]]
- 出力
- [[3, 0, 1], [0, 0, 0], [2, 0, 4]]
- 説明
- 唯一的 0 位于第 1 行、第 1 列。第 1 行变为全 0，第 1 列也一样，这会将 8 和 6 变为 0。四个角都不在这两条线上，因此保持原值。
- 入力
- matrix = [[0, 4, 2, 0], [9, 3, 5, 1], [6, 1, 0, 8]]
- 出力
- [[0, 0, 0, 0], [0, 3, 0, 0], [0, 0, 0, 0]]
- 説明
- 0 行目（列 0 と 3）および 2 行目（列 2）のゼロによって、0 行目と 2 行目、さらに列 0、2、3 がクリアされます。1 行目では列 1 の 3 が残ります。書き込んだゼロは広がりません。
発展問題
以下の最適な方法では、追加の真偽値を2つ保持します。matrix[0][0]を最初の行の代わりとして使い、1つだけで済ませられますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
最初の例で、0を見つけた瞬間に行と列を消してみてください。4つの角のうち3つが消えるのはなぜでしょうか？
セルが最終的に 0 になるのは、開始時点でその行または列に 0 が含まれていた場合に限られます。まず読み取りだけを行うパスで該当する行と列を記録し、次のパスで書き込みます。
O(1) の追加領域で済ませるには、記録を行列内に保持します。最初の列には各行につき1つのセルがあり、最初の行には各列につき1つのセルがあります。これらを使う前に、最初の行と最初の列にそれぞれ独自の 0 があるかどうかを2つのブール値で記録し、最後にそれらをクリアします。
解説
自分で書き込んだ 0 は、もともと与えられていた 0 とまったく同じに見えるため、走査中に行をクリアすると、行列全体に 0 が広がってしまいます。読み取りと書き込みを分けましょう。まず、どの行と列に 0 があったかを記録してから、それらをクリアします。その記録は 2 つの配列に保持するか、追加の領域を O(1) に抑えるために、行列自体の最初の行と列に保持します。
2つの配列で行と列に印を付ける
考え方
あるセルがちょうど0になるのは、開始時にその行または列に0が含まれていた場合です。書き込みを行わない走査で、zeroRow[i]とzeroCol[j]という2つの事実のリストを記録し、その後、行または列に印が付いているすべてのセルをクリアします。最初の書き込みより前にすべての読み取りが完了するため、影響が広がることはありません。
各走査ではm·n個のセルを1回ずつ調べるため、時間計算量はO(m·n)で、配列にはm + n個の真偽値が格納されます。
アルゴリズム
- m 個の要素を持つ
zeroRowと、n 個の要素を持つzeroColを作成し、すべて false にします。 - すべてのセルを走査します。
matrix[i][j]が 0 の場合、zeroRow[i]とzeroCol[j]を true に設定します。 - もう一度すべてのセルを走査し、
zeroRow[i]またはzeroCol[j]が true の場合、そのセルを 0 に設定します。 - 行列を返します。
def setZeroes(matrix):
m, n = len(matrix), len(matrix[0])
zero_row = [False] * m
zero_col = [False] * n
# Pass 1: only read, so a new zero can never spread further.
for i in range(m):
for j in range(n):
if matrix[i][j] == 0:
zero_row[i] = True
zero_col[j] = True
# Pass 2: write.
for i in range(m):
for j in range(n):
if zero_row[i] or zero_col[j]:
matrix[i][j] = 0
return matrix最初の行と列を目印として使用します
考え方
最初の列には各行につき1つ、最初の行には各列につき1つのセルがあり、これらが2つのマーカー配列の形になります。そのため、行 i、列 j の値が0なら、matrix[i][0] と matrix[0][j] に0を書き込みます。情報は失われません。これらのセルはどちらも、いずれにせよ0にする必要がある行または列に属しているためです。
行0と列0はデータであると同時にマーカーでもあり、そこにマーカーを書き込むと、もともとその位置に0があったかどうかが分からなくなります。そのため、まず確認して結果を2つのブール値に保存します。i ≥ 1 かつ j ≥ 1 のセルだけにマークを付けて値を変更し、行0と列0は最後にクリアします。値の変更処理でこれらを読み取るためです。
2つ目の例では、行1、列1の3は残ります。そのマーカーである matrix[1][0] = 9 と matrix[0][1] = 4 が0ではないためです。追加メモリを2つのブール値に抑えたまま、時間計算量は O(m·n) です（Rでは、最初に入力をコピーするため O(m·n) です）。
アルゴリズム
- 行 0 に 0 が含まれている場合は
firstRowZeroを、列 0 に 0 が含まれている場合はfirstColZeroを設定します。 i ≥ 1かつj ≥ 1であるすべてのセルのうち、値が 0 のセルについて、matrix[i][0]とmatrix[0][j]を 0 に設定します。i ≥ 1かつj ≥ 1であるすべてのセルについて、matrix[i][0]またはmatrix[0][j]が 0 の場合、そのセルを 0 に設定します。firstRowZeroが真の場合、行 0 を 0 に設定します。firstColZeroが真の場合、列 0 を 0 に設定します。- 行列を返します。
def setZeroes(matrix):
m, n = len(matrix), len(matrix[0])
# The first row and column will hold the markers, so remember first
# whether they need to become zero themselves.
first_row_zero = any(matrix[0][j] == 0 for j in range(n))
first_col_zero = any(matrix[i][0] == 0 for i in range(m))
# Mark: a zero inside the matrix flags its row in column 0
# and its column in row 0.
for i in range(1, m):
for j in range(1, n):
if matrix[i][j] == 0:
matrix[i][0] = 0
matrix[0][j] = 0
# Fill the inside from the markers.
for i in range(1, m):
for j in range(1, n):
if matrix[i][0] == 0 or matrix[0][j] == 0:
matrix[i][j] = 0
# The marker row and column go last.
if first_row_zero:
for j in range(n):
matrix[0][j] = 0
if first_col_zero:
for i in range(m):
matrix[i][0] = 0
return matrix
落とし穴と境界ケース
- 0を見つけた時点ですぐに行と列をクリアする。最初の例では、行1、列2に新しい0ができると、列2がクリアされ、左上の3だけが残る。
matrix[0][0]で行0と列0の両方をマークしてしまう。[[1, 2, 3], [0, 5, 6], [7, 8, 9]]では、列0の0によって行0まで誤ってクリアされる。- 値を埋める前に行0または列0をクリアする。
[[0, 2, 3], [4, 5, 6], [7, 8, 9]]では、すべての列がマークされているように見え、行列全体が0になる。 - 単一行の場合を忘れる。行が1つの場合、1から始まるループは何もしないため、処理はブール値にすべて委ねられる。
[[1, 0, 3]]は[[0, 0, 0]]にならなければならない。
よくある質問3
行列を走査しながら、なぜゼロを設定できないのですか？
自分で書いた 0 は、元からある 0 と同じように見えます。スキャンがそれに到達すると、その行と列を消去し、新たにできたゼロがさらに広がります。セルを変更する前に、元からあるゼロをすべて記録してください。
Set Matrix Zeroes の時間計算量はどれくらいですか？
m × n 行列に対して O(m·n) です。すべてのセルが定数回読み書きされるためです。どのセルも答えを変える 0 である可能性があるため、これより高速な解法はありません。追加領域は、マーカー配列を使う場合は O(m + n)、最初の行と列をマーカーとして使う場合は O(1) です。
0の代わりに特別な値でセルに印を付けられますか？
一部の解法では、消去するセルにプレースホルダーを書き込み、最後にプレースホルダーをゼロに置き換えます。これは、入力にプレースホルダーが決して現れない場合にのみ機能しますが、整数行列でそれが保証されることはほとんどありません。また、0 ごとに行と列に沿って書き込むと、O(m·n·(m + n)) の時間がかかります。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def setZeroes(matrix):
# ここにコードを書いてくださいテスト #1
テスト #2
引数
matrix = [[3, 8, 1], [5, 0, 7], [2, 6, 4]]
期待される出力
[[3, 0, 1], [0, 0, 0], [2, 0, 4]]