[leetcode] 240. 2D Matrix II @pythonを検索します

240 Search 2d Matrix Ii Python

元の質問

m xn行列の値を検索する効率的なアルゴリズムを記述します。このマトリックスには、次のプロパティがあります。

各行の整数は、左から右に昇順でソートされます。
各列の整数は、上から下に昇順で並べ替えられます。
例：

次のマトリックスについて考えてみます。

[
[1、4、7、11、15]、
[2、5、8、12、19]、
[3、6、9、16、22]、
[10、13、14、17、24]、
[18、21、23、26、30]
]
target = 5の場合、trueを返します。

ターゲット= 20の場合、falseを返します。

解決策1

行の反復に従って、ターゲットが行にあるかどうかを確認します。
時間：O（m * n）
スペース：O（1）

コード

class Solution(object): def searchMatrix(self, matrix, target): ''' :type matrix: List[List[int]] :type target: int :rtype: bool ''' for row in matrix: if target in row: return True return False

解決策2

質問の意味に従って、各行と列は昇順であり、最初のr = 0、c = n-1を定義します。ターゲットがmatrix [r] [c]と正確に等しい場合、targetがmatrix [r] [c]より大きい場合は直接戻り、matrix [r] [c]であるため、この行には含まれません。はその行の最大値であるため、ターゲットがmatrix [r] [c]より小さい場合は次の行に進みます。次に、matrix [r] [c]はの最小値であるため、この列には含まれません。その列なので、前の列に移動して見つけます。

時間：O（m + n）
スペース：O（1）

コード

class Solution(object): def searchMatrix(self, matrix, target): ''' :type matrix: List[List[int]] :type target: int :rtype: bool ''' # base case if not matrix: return False m, n = len(matrix), len(matrix[0]) r, c = 0, n-1 while r < m and c >=0: if matrix[r][c] == target: return True if matrix[r][c] < target: # go to next row r += 1 else: # go to prev col c -= 1 return False