代碼思路:
“根節點” 對應的是矩陣的 “左下角” 和 “右上角” 元素,以 matrix 中的左下角元素為標志數 flag ,則有:
若 flag > target ,則 target 一定在 flag 所在行的上方 ,即 flag 所在行可被消去,i–
若 flag < target ,則 target 一定在 flag 所在 列的右方 ,即 flag 所在列可被消去,j++
算法流程:
從矩陣 matrix 左下角元素(索引設為 (i, j) )開始遍歷,并與目標值對比:
當 matrix[i][j] > target 時,執行 i-- ,即消去第 i 行元素。
當 matrix[i][j] < target 時,執行 j++ ,即消去第 j 列元素。
當 matrix[i][j] = target 時,返回 true ,代表找到目標值。
class Solution:def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:i,j = len(matrix)-1,0while i >= 0 and j < len(matrix[0]):if matrix[i][j] > target: i-=1elif matrix[i][j] < target: j+=1else:return Truereturn False