74. 搜索二维矩阵#

今天我要带大家攻克一道非常有趣的题目 - LeetCode 74「搜索二维矩阵」。这道题乍看有点唬人，但用我们玩数独游戏的思维去理解，你会发现它其实很优雅！

🎮 从数独游戏说起#

还记得玩数独时，我们要在9×9的格子里查找数字吗？每次找数字时，我们都会先看这个数字可能在哪一行，然后再在那一行中定位。今天的题目就像是在玩一个简化版的数独，只不过格子里的数字是有规律排列的！

问题描述#

题目目标#

给你一个满足以下条件的 m x n 整数矩阵 matrix ：每行中的整数从左到右按升序排列，且每行的第一个整数大于前一行的最后一个整数。给定一个目标值 target ，判断 target 是否在矩阵中。

示例 1#

输入： matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 输出： true 网格示意：

 1  3  5  7
10 11 16 20
23 30 34 60

text

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

💡 问题本质探索#

题目要求：在一个m×n的矩阵中搜索一个目标值。这个矩阵有两个特点：

每行从左到右是升序的
每一行的第一个数都大于上一行的最后一个数

让我们看个具体例子：

matrix = [
  [1,  3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 60]
]
target = 3

返回 true （因为3在矩阵中）

plaintext

🤔 深入思考#

这个矩阵有什么特别之处？让我们仔细观察：

从左上角到右下角是严格递增的
把矩阵”拉直”后就是一个排序数组！

这个发现太关键了！它提示我们可以把二维搜索转化为一维搜索。

🚀 优雅的解决方案#

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        // 边界处理：矩阵为空、行数为0、或列数为0时，直接返回 false
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }

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

        // 将二维矩阵“逻辑上拉直”为长度 m*n 的有序一维数组
        int left = 0; // 一维搜索左边界（包含）
        int right = m * n - 1; // 一维搜索右边界（包含）

        // 在一维下标区间 [left, right] 上做标准二分查找
        while (left <= right) {
            int mid = left + (right - left) / 2; // 中间一维下标，防止溢出写法

            // 关键映射：把一维下标 mid 还原为二维坐标 (row, col)
            int row = mid / n;  // 行号 = 下标 / 列数
            int col = mid % n;  // 列号 = 下标 % 列数

            int value = matrix[row][col]; // 取出当前位置对应的矩阵值

            // 比较当前值与目标值，决定下一步搜索方向
            if (value == target) {
                // 找到目标值
                return true;
            } else if (value < target) {
                // 当前值偏小，目标只能在右半区
                left = mid + 1;
            } else {
                // 当前值偏大，目标只能在左半区
                right = mid - 1;
            }
        }

        // 搜索结束仍未命中，说明目标值不存在
        return false;
    }
}

java

📝 解题思路全解析#

1. 坐标转换的智慧#

这个解法最精妙的地方在于坐标转换：

一维索引 = 行 × 列数 + 列
反过来：行号 = 一维索引 / 列数
列号 = 一维索引 % 列数

就像我们在实际生活中把二维的街道地址转换成一维的门牌号！

2. 二分查找的应用#

有了坐标转换，问题就变成了普通的二分查找：

把矩阵看作一个长度为 m×n 的有序数组
用二分查找在这个”虚拟”的一维数组中搜索
需要时再把一维索引转回二维坐标

3. 边界处理#

要特别注意以下边界情况：

矩阵为空
矩阵只有一行或一列
目标值在范围之外

💡 优化思维进阶#

方案一：传统二分（上述方案）#

时间复杂度：O(log(m×n)) 空间复杂度：O(1)

方案二：两次二分#

可以先对第一列二分查找确定行，再在目标行中二分查找：

public boolean searchMatrix(int[][] matrix, int target) {
    int m = matrix.length; // 行数
    int n = matrix[0].length; // 列数

    // 第一步：在“每行首元素”上二分，锁定可能包含 target 的行
    int top = 0, bottom = m - 1; // 行搜索区间 [top, bottom]
    while (top < bottom) {
        // 取上中位，避免 top = mid 时死循环
        int mid = (bottom + top + 1) / 2;
        // 如果该行首元素 <= target，说明目标行在 mid 或其下方
        if (matrix[mid][0] <= target) {
            top = mid;
        } else {
            // 否则目标行一定在 mid 上方
            bottom = mid - 1;
        }
    }

    // 第二步：在锁定的这一行内做普通二分查找
    int row = top; // 目标候选行
    int left = 0, right = n - 1; // 列搜索区间 [left, right]
    while (left <= right) {
        int mid = left + (right - left) / 2; // 当前列中点
        if (matrix[row][mid] == target) {
            // 命中目标
            return true;
        } else if (matrix[row][mid] < target) {
            // 当前值偏小，向右半区继续找
            left = mid + 1;
        } else {
            // 当前值偏大，向左半区继续找
            right = mid - 1;
        }
    }

    // 行内搜索结束未找到
    return false;
}

java

🎯 相关题目引申#

搜索二维矩阵 II（LeetCode 240）
- 类似但矩阵只保证行列有序
- 需要不同的搜索策略
有序矩阵中的第k小元素（LeetCode 378）
- 利用类似的矩阵性质
- 但需要结合二分查找和计数

🌟 面试常见追问#

如何处理重复元素？
- 当前题目不涉及重复元素
- 但可以考虑查找第一个/最后一个位置
能否优化空间复杂度？
- 当前方案已经是O(1)空间复杂度
- 主要优化点在于减少不必要的计算
如果矩阵很大，如何优化？
- 考虑分块处理
- 可以使用并行计算