文章目录

leetcode240. 搜索二维矩阵 II方法：利用矩阵排序的性质寻找思路：代码：结果：

leetcode240. 搜索二维矩阵 II

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：

每行的元素从左到右升序排列。每列的元素从上到下升序排列。

示例:

现有矩阵 matrix 如下：

[ [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。

给定 target = 20，返回 false。

---

方法：利用矩阵排序的性质寻找

思路：

这个方法中，我们试图从matrix的一个点出发，根据与target的大小关系，来对矩阵进行遍历，直到找到target，或越界。

由矩阵的性质，每一行每一列都是升序的，左上角和右下角是矩阵的最小和最大值。

我们的习惯是从最小或最大值开始，也就是左上角或右下角，但是本题不能这样，原因是，**从左上角开始，如果target大于目前的值，无论是向右走还是向左走，值都是变大，我们无法判断应该怎么走可以找到target，只能使用递归dfs对两种方法都进行，但是每深入一层，都会有两个选择，会导致超时。**右下角同理。

而如果从左下角或右上角开始，就可以遍历矩阵的所有值，且每次的选择是固定的。我们以左下角为例，向右走值增大，向上走值减小，如果左下角的值大于target，那么说明最后一行所有值都大于target，不能往右走，只能往上走；如果左下角值小于target，说明第一列的所有值都小于target，只能往右走；如果值等于target，直接返回True即可。

因此我们从左下角开始遍历，直到坐标指针越界，说明没找到，返回False。

下面几张图的例子展示了这个过程。

​

​

​

代码：

class Solution: def searchMatrix(self, matrix, target): """ :type matrix: List[List[int]] :type target: int :rtype: bool """ #如果matrix为[]或[[]]，返回False if not matrix or not matrix[0]: return False m = len(matrix) n = len(matrix[0]) #初始位置在左下角 x = m-1 y = 0 while 0 <= x < m and 0 <= y < n: #找到直接返回True if matrix[x][y] == target: return True #target更大，向右 elif matrix[x][y] < target: y += 1 #target更小，向左 else: x -= 1 #没找到，返回False return False

结果：