【LeetCode 热题100】 240. 搜索二维矩阵 II的算法思路及python代码

240. 搜索二维矩阵 II

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

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

示例 1：

输入：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

示例 2：

输入：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 = 20
输出：false

解题思路：

该算法采用深度优先搜索（DFS） 结合栈结构，从矩阵的中间位置开始搜索。利用矩阵行列递增的特性，根据当前元素与目标值的比较结果，向可能的方向扩展搜索。通过记录已访问的位置避免重复检查，直到找到目标值或遍历完所有可能路径。

算法步骤

初始化

获取矩阵的行数 m 和列数 n，选择中间位置 (m//2, n//2) 作为起点，压入栈中。

栈处理

循环处理栈中的位置，直到栈为空：

• 弹出栈顶元素，检查是否越界，若越界则跳过。
• 若当前元素等于目标值，返回 True。
• 若当前元素大于目标值，将上方 (i-1, j) 和左方 (i, j-1) 压入栈。
• 若当前元素小于目标值，将下方 (i+1, j) 和右方 (i, j+1) 压入栈。
• 标记当前位置为已访问，避免重复处理。

终止条件

若栈空仍未找到目标值，返回 False。

python代码

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m = len(matrix)
        n = len(matrix[0])
        i,j = m // 2, n // 2
        stack = [[i,j]]
        path_ij = []
        while len(stack) > 0:
            current_ij = stack.pop()
            i,j = current_ij[0], current_ij[1]
            if i < 0 or j < 0 or i >= m or j >= n:
                continue
            current_ele = matrix[i][j]
            if current_ele > target and current_ij not in path_ij:
                stack.append([i-1,j])
                stack.append([i,j-1])
            elif current_ele < target and current_ij not in path_ij:
                stack.append([i+1,j])
                stack.append([i,j+1])
            elif current_ele == target:
                return True
            path_ij.append(current_ij)
        return False

结果

复杂度分析

时间复杂度：
最坏情况下需遍历大部分矩阵元素。每次判断是否已访问的时间为 $O(k)$（k 为已访问节点数），整体最坏时间复杂度为 $O(mn\ast (m+n))$，效率较低。
空间复杂度：
栈和已访问列表最多存储 $O(mn)$ 个元素，空间复杂度为 $O(mn)$。

官方题解思想

基于矩阵行列递增的特性，从右上角开始逐步缩小搜索范围。通过比较当前元素与目标值的大小，动态调整搜索方向：

• 若当前元素大于目标值，说明目标值不可能在当前元素的右侧列，因此向左移动一列。
• 若当前元素小于目标值，说明目标值不可能在当前元素的上方行，因此向下移动一行。

通过这种“逐步排除”策略，快速逼近目标值，实现高效搜索。

算法步骤

• 初始化起点： 从矩阵的右上角[0, n-1]开始搜索。
• 循环搜索：
  • 若当前元素等于目标值，直接返回 True。
  • 若当前元素大于目标值，向左移动一列 y -= 1。
  • 若当前元素小于目标值，向下移动一行 x += 1。
• 终止条件： 当行或列索引越界时，说明目标值不存在，返回 False。

python代码

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m, n = len(matrix), len(matrix[0])
        x, y = 0, n - 1
        while x < m and y >= 0:
            if matrix[x][y] == target:
                return True
            if matrix[x][y] > target:
                y -= 1
            else:
                x += 1
        return False

结果

复杂度分析：

• 时间复杂度：$O(m+n)$
  最坏情况下从右上角移动到左下角，总移动次数不超过 $m+n$ 次，例如从 $(0,n-1)$ 移动到 $(m-1,0)$。
• 空间复杂度：$O(1)$
  仅使用常数级别的额外空间（指针 $x,y$）。