LeetCode Algorithm 240. 搜索二维矩阵 II

240. 搜索二维矩阵 II

Ideas

这题我记得在左神算法初级班里面有。

主要的思想就是定义两个指针row_index和col_index，从右上角开始逐个搜索。

如果matrix[row_index][col_index] < target，说明当前遍历的元素比较小，需要往下一行去搜索。

如果matrix[row_index][col_index] > target，说明当前遍历的元素比较大，需要往前一列去搜索。

如果matrix[row_index][col_index] == target，说明找到了，直接返回True。

最后如果两个指针越界了那就说明target不在matrix中，返回False。

为什么从右上角开始逐个搜索而不是从左上角开始搜索呢？

假如从左上角开始搜索，因为matrix[0][0]位置的元素是最小的，所以如果matrix[row_index][col_index] < target，那么到底是往下一列走还是往下一行走呢，不好确定，所以从右上角开始搜索。

Code Python

from typing import List class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: rows, cols = len(matrix), len(matrix[0]) row_index, col_index = 0, cols - 1 while row_index < rows and col_index > -1: if matrix[row_index][col_index] < target: row_index += 1 elif matrix[row_index][col_index] > target: col_index -= 1 else: return True return False