240. 搜索二维矩阵 II

一、题目

240. 搜索二维矩阵 II

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。

该矩阵具有以下特性：

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

二、题解

思路：从右上角开始搜索。

因为矩阵满足：

  • 每一行从左到右递增；
  • 每一列从上到下递增。

所以我们可以从矩阵的 右上角 开始查找。

1. 核心思路

假设当前元素是 matrix[row][col]。

由于我们从右上角开始：

  • 当前元素左边的数都比它小；
  • 当前元素下面的数都比它大。

因此：

  1. 如果当前值等于 target，说明找到了，直接返回 true。
  2. 如果当前值大于 target，说明当前值太大，需要向左移动。
  3. 如果当前值小于 target，说明当前值太小，需要向下移动。

这样每次都可以排除一整行或一整列。

2. 具体步骤

  1. 定义两个指针：
    • row = 0，表示从第一行开始；
    • col = n - 1，表示从最后一列开始。
  2. 当 row < m && col >= 0 时，继续搜索。
  3. 比较当前值 matrix[row][col] 和 target：
    • 如果相等，返回 true；
    • 如果当前值大于 target，说明这一列太大，col--；
    • 如果当前值小于 target，说明这一行太小，row++。
  4. 如果越界后还没有找到，返回 false。

3. 关键逻辑

例如查找 target = 5：

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

从右上角 15 开始：

15 > 5，向左
11 > 5，向左
7  > 5，向左
4  < 5，向下
5 == 5，找到

三、代码

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        // 处理空矩阵的情况
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }

        int m = matrix.length;
        int n = matrix[0].length;

        // 从右上角开始搜索
        int row = 0;
        int col = n - 1;

        while (row < m && col >= 0) {
            int cur = matrix[row][col];

            if (cur == target) {
                // 找到目标值
                return true;
            } else if (cur > target) {
                // 当前值太大，说明这一列下面的值更大，不可能有答案
                // 所以向左移动
                col--;
            } else {
                // 当前值太小，说明这一行左边的值更小，不可能有答案
                // 所以向下移动
                row++;
            }
        }

        // 越界后仍然没有找到，说明不存在
        return false;
    }
}

四、复杂度分析

时间复杂度：O(m+n)O(m + n)

说明：每次移动只会向左或向下，最多向左移动 n 次，向下移动 m 次。

空间复杂度：O(1)O(1)

说明：只使用了常数个额外变量。

评论