NeetCodeのSolutionを書いていく #
Search a 2D Matrix #
https://neetcode.io/problems/search-2d-matrix
neetcode.io
問題概要 #
m x n の2次元配列matrixと整数targetが与えられます。 それぞれの行は昇順で並べられています。 すべての行の最初の整数が前の行の最後の整数より大きいです。 targetがあればTrueをなければFalseを返しなさい。
例 #
Input: matrix = [[1,2,4,8],[10,11,12,13],[14,20,30,40]], target = 10 Output: true
Input: matrix = [[1,2,4,8],[10,11,12,13],[14,20,30,40]], target = 15 Output: false
制約 #
- m は matrix.length
- n は matrix[i].length
- m,n は 1以上100以下
- matrix[i][j], target は -10000以上10000以下
計算時間：O(log(m * n)) メモリ：O(1)
メモ #
ソート済みなので、targetが含まれていそうなrowをバイナリサーチで探す≒O(logm)、見つけたrowからtargetを探す≒O(logn)でO(logm*n)?
from typing import List
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
# 行を2分探索で探す
low, high = 0, len(matrix) - 1
while low <= high:
r = (low + high) // 2
min_val = matrix[r][0]
max_val = matrix[r][-1]
if min_val <= target <= max_val:
break
elif target < min_val:
high = r - 1
else:
low = r + 1
else:
return False # 行が見つからなかった
# 列を2分探索で探す
row = matrix[r]
low, high = 0, len(row) - 1
while low <= high:
c = (low + high) // 2
v = row[c]
if v == target:
return True
elif target < v:
high = c - 1
else:
low = c + 1
return False