Search a 2D Matrix
m 行 n 列の整数グリッド matrix と、整数 target が与えられます。各行は昇順に並んでおり、各行の先頭の値は、その1つ上の行の末尾の値より大きくなっています。target がグリッド内にあれば true、なければ false を O(log(m × n)) 時間で返してください。
関数
- matrixinteger-2d-array
- 行ごとに並べた、行のリストとして与えられるグリッド
- targetinteger
- 探す値
- 戻り値boolean
- target がグリッド内にある場合は true、そうでない場合は false
制約
1 ≤ m, n ≤ 100。ここで、m = matrix.length、n = matrix[i].lengthです。- すべての行の長さは同じで、
nです。 -104 ≤ matrix[i][j], target ≤ 104- 各行は厳密な昇順に並んでおり、各行の最初の値は前の行の最後の値より大きくなっています。
例
- 入力
- matrix = [[2, 5, 9, 14], [17, 21, 26, 30], [33, 38, 45, 52]]target = 26
- 出力
- true
- 説明
- 行ごとに読むと、12個の値は1つのソート済みリストです。位置0から11を対象に二分探索すると、位置5の21（小さすぎる）、位置8の33（大きすぎる）を確認し、その後、位置6で26を見つけます。
- 入力
- matrix = [[2, 5, 9, 14], [17, 21, 26, 30], [33, 38, 45, 52]]target = 16
- 出力
- false
- 説明
- 16 は、行 0 の最後の値である 14 の後、行 1 の最初の値である 17 の前に来ます。その間には何もないため、16 はグリッド内にありません。
発展問題
行の長さが異なっていても、端から端までソートされているとします。位置を行と列に変換するにはどうすればよいでしょうか。また、検索コストはどのくらいでしょうか。
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
行列を、長い1つのリストであるかのように、行ごとに左から右へ読んでください。そのリスト内の値の順序について、何に気づきますか？
この2つのルールを合わせると、行ごとに読んだ行列全体が、
m × n個の値からなる1つのソート済みリストであることを意味します。行列を実際に作らなくても、二分探索できます。位置
0からm × n - 1までを二分探索します。位置pは行p / n、列p % nにあります（整数除算）。各ステップでセルを1つ読み取り、残りの位置の半分を除外します。
解説
この2つの順序規則を組み合わせると、行ごとに読んだとき、グリッドはm × n個の値を並べた1つのソート済みリストになります。位置を使ってそのリストを二分探索し、1回の除算で各位置を行と列に戻します。すると、100×100のグリッドでは、10000回ではなく最大14回の比較で済みます。
すべてのセルを確認してください
考え方
すべてのセルをtargetと比較し、一致したらtrueを、最後のセルまで確認しても一致しなければfalseを返します。すべてのセルを読み取るため、ソートされているかどうかにかかわらず、どのようなグリッドでも正しく動作します。順序は一切利用しないため、100×100のグリッドでは最大10000回の比較が必要です。
アルゴリズム
matrixの各行について、各値を順番に確認します。- 値が
targetと等しい場合、trueを返します。 - ループの後で、
falseを返します。
def searchMatrix(matrix, target):
for row in matrix:
for value in row:
if value == target:
return True
return False右上隅から歩く
考え方
右上のセルから見ると、左にある値はすべて小さく、下にある値はすべて大きくなります。セルの値がtargetより大きければ、その下の列も大きいので、左に移動してその列を候補から外します。小さければ、その左の行も小さいので、下に移動してその行を候補から外します。
最初の例では、14は26より小さいため、下に移動して30を見ます。30は大きいため、左に移動して26を見つけます。各ステップで行または列を1つ除外するので、必要なステップ数は最大でもm + nです。100×100のグリッドなら200ステップです。この探索では行と列がソートされていればよいため、このグリッドが持つ情報の半分は使いません。
アルゴリズム
- 行
0の最後の列から始めます。 - 行と列がグリッド内にある間、セルを読み取ります。
- それが
targetと等しければ、trueを返します。 - それがより大きければ列を1つ左に移動し、より小さければ行を1つ下に移動します。
- グリッドの外に出たら、
falseを返します。
def searchMatrix(matrix, target):
# Start at the top-right corner: left is smaller, down is larger.
r, c = 0, len(matrix[0]) - 1
while r < len(matrix) and c >= 0:
value = matrix[r][c]
if value == target:
return True
if value > target:
c -= 1 # every value below in this column is larger still
else:
r += 1 # every value to the left in this row is smaller still
return False平坦化したグリッドに対する二分探索
考え方
セルに行ごとに番号を付けます。行 0 には位置 0 から n - 1 まで、行 1 には n から 2n - 1 までが入り、以降も同様です。各行はソートされており、前の行が終わった位置より上から始まるため、位置が進むにつれて値も大きくなります。これはソート済みリストなので、二分探索を適用できます。
リストを作成する必要はありません。位置 p は行 p / n、列 p % n にあり、ここでは整数除算を使います。最初の例では n = 4 なので、位置 6 は行 1、列 2 にあり、そこには 26 が入っています。比較のたびに、target が入っている可能性のある位置は半分になります。10000 個のセルなら最大 14 回で、追加メモリはインデックス 2 つ分です。
アルゴリズム
mとnをそれぞれ行数と列数とし、lo = 0、hi = m × n - 1と設定します。lo ≤ hiの間、両者の中間にある値をmidとします。value = matrix[mid / n][mid % n]を読み取ります。valueがtargetと等しければ、trueを返します。より小さければ、lo = mid + 1と設定します。それ以外の場合は、hi = mid - 1と設定します。- ループが終了したら、
falseを返します。
def searchMatrix(matrix, target):
rows, cols = len(matrix), len(matrix[0])
# Read row by row, the cells form one sorted list of rows * cols values.
# Position p of that list is matrix[p // cols][p % cols].
lo, hi = 0, rows * cols - 1
while lo <= hi:
mid = (lo + hi) // 2
value = matrix[mid // cols][mid % cols]
if value == target:
return True
if value < target:
lo = mid + 1
else:
hi = mid - 1
return False
落とし穴と境界ケース
- 列数ではなく行数で割っている。位置
pは行p / nにある。nの代わりにmを使うと、正方形のグリッドではコードが正しく動くが、3行4列では失敗する。 - 2回探索する方法で、
targetがmatrix[0][0]より小さい場合を処理していない。そこ以下から始まる行はなく、行インデックス-1が2回目の探索に渡される。 hiを含む範囲なのに、lo < hiを条件にループしている。targetを含む1行1列のグリッドでは、ループが一度も実行されないためfalseが返る。- LuaとRで、インデックスが1から始まることによるずれを忘れている。位置
pは行p / n + 1、列p % n + 1となる。
よくある質問3
2D行列を検索する時間計算量はどれくらいですか？
平坦化したグリッドに対する二分探索は、O(log(m × n))時間、O(1)空間で実行できます。10000個のセルなら比較回数は最大14回です。log(m × n) = log m + log nなので、行を探してからその行の中を探す方法と同じです。
右上隅からの探索と二分探索のどちらを使うべきでしょうか？
角をたどる方法では O(m + n) ステップかかり、行と列がソートされているだけでよいため、ある行がその上の行の末尾より下から始まる場合の変形版も解けます。ここでのように、各行の開始位置が前の行の終了位置より上にある場合は、二分探索のほうが高速です。
二分探索を2回、つまり行を検索するものと、その行の中を検索するものを行う方法も正しいですか？
はい。最初の列を二分探索して、最初の値がtarget以下である最後の行を見つけ、その行を二分探索します。計算量はO(log m + log n)で、同じです。単一の探索でも同じ処理を1つのループで行え、エッジケースも少なくなります。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def searchMatrix(matrix, target):
# ここにコードを書いてくださいテスト #1
テスト #2
引数
matrix = [[2, 5, 9, 14], [17, 21, 26, 30], [33, 38, 45, 52]] target = 26
期待される出力
true