240. 搜索二维矩阵II#

生活中的搜索策略#

想象你在一个大型图书馆里找书。这个图书馆的书架是按照两个维度排列的：每个书架从左到右按书名字母顺序排列，从上到下的书架则按照出版年份排序。如果你要找一本特定的书，你会怎么做？显然，从第一个书架第一本书开始一本本查找是最笨的方法。聪明的做法是：先找到可能的书架（年份范围），再在书架上快速定位（利用字母顺序）。

问题描述#

题目目标#

LeetCode第240题”搜索二维矩阵 II”是这样描述的：编写一个程序，在一个 m x n 的矩阵中查找一个值 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

text

输出： true 矩阵示意：

 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

text

说明： 图示把输入结构和输出结果并排展开后，会更容易直接看清题目的变化过程。

补充说明#

矩阵按行给出，外层数组表示所有行，内层数组表示每一行的元素。

最直观的解法：暴力搜索#

就像在图书馆里一本本翻找，最简单的方法是遍历矩阵中的每个元素。虽然这种方法保证能找到答案，但效率很低。

暴力搜索的实现#

public boolean searchMatrix(int[][] matrix, int target) {
    // 边界条件：矩阵为空、没有行、或没有列时，不可能找到目标值
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
        return false;
    }

    // m 表示矩阵行数
    int m = matrix.length;
    // n 表示矩阵列数
    int n = matrix[0].length;

    // 双重循环暴力遍历每一个元素
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            // 当前元素等于目标值，立即返回 true
            if (matrix[i][j] == target) {
                return true;
            }
        }
    }

    // 遍历结束仍未找到，返回 false
    return false;
}

java

优化解法：从右上角开始搜索#

仔细观察矩阵的特性，我们可以采用更聪明的方法。就像在图书馆找书时，我们可以站在一个特殊的位置 —— 右上角，这个位置很神奇：

向左看，数字会变小
向下看，数字会变大

这就给了我们一个明确的搜索方向！

右上角搜索的原理#

想象你在玩一个猜数字的游戏：

站在右上角
如果当前数字大于目标值，就向左移动（因为下面的数字更大，没必要看）
如果当前数字小于目标值，就向下移动（因为左边的数字更小，没必要看）
如果相等，就找到了答案

示例运行#

以查找target = 9为例：

1  4  7  11 [15] → 比9大，左移
1  4  7 [11] 15  → 比9大，左移
1  4 [7]  11 15  → 比9小，下移
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

plaintext

Java代码实现#

public boolean searchMatrix(int[][] matrix, int target) {
    // 边界条件：空矩阵或空列，直接返回 false
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
        return false;
    }

    // row 表示当前所在行，初始在第一行（最上面）
    int row = 0;
    // col 表示当前所在列，初始在最后一列（最右边）
    // 这样起点位于“右上角”，便于利用有序性剪枝
    int col = matrix[0].length - 1;

    // 只要 row/col 仍在矩阵有效范围内，就继续搜索
    while (row < matrix.length && col >= 0) {
        // 情况1：命中目标值，直接返回 true
        if (matrix[row][col] == target) {
            return true;
        // 情况2：当前值比目标大
        // 因为当前列从上到下递增，往下只会更大；所以应向左缩小值
        } else if (matrix[row][col] > target) {
            // 列左移一格
            col--;
        // 情况3：当前值比目标小
        // 因为当前行从左到右递增，往左只会更小；所以应向下增大值
        } else {
            // 行下移一格
            row++;
        }
    }

    // 越界仍未找到，说明目标值不存在
    return false;
}

java

解法比较#

让我们比较这两种方法：

暴力搜索：

时间复杂度：O(m×n)
空间复杂度：O(1)
优点：简单直观，容易实现
缺点：没有利用矩阵的特性，效率低

右上角搜索：

时间复杂度：O(m+n)
空间复杂度：O(1)
优点：充分利用矩阵特性，高效快速
缺点：需要理解矩阵的排序特性

实用技巧总结#

解决矩阵搜索问题的关键点：

观察矩阵的特性（如排序规律）
寻找特殊位置（如右上角）作为起点
利用排序特性确定搜索方向
正确处理边界条件

小结#

通过搜索二维矩阵这道题，我们学会了如何在有序矩阵中高效搜索。这种思维方式不仅能解决算法题，在数据库索引设计、图像处理等领域都有应用。记住，当遇到需要在有序数据结构中搜索的问题时，可以考虑利用数据的有序性来优化搜索过程，通常能获得比暴力搜索更好的性能！