忍者算法

Appearance

图解搜索二维矩阵：一次"数独探险"！ ​

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

🎮 从数独游戏说起 ​

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

💡 问题本质探索 ​

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

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

让我们看个具体例子：

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

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

🤔 深入思考 ​

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

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

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

🚀 优雅的解决方案 ​

java
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 left = 0;
        int right = m * n - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            // 关键转换：从一维索引还原二维坐标
            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;
    }
}

📝 解题思路全解析 ​

1. 坐标转换的智慧 ​

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

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

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

2. 二分查找的应用 ​

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

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

3. 边界处理 ​

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

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

💡 优化思维进阶 ​

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

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

方案二：两次二分 ​

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

java
public boolean searchMatrix(int[][] matrix, int target) {
    int m = matrix.length;
    int n = matrix[0].length;
    
    // 先二分查找第一列，确定目标所在行
    int top = 0, bottom = m - 1;
    while (top < bottom) {
        int mid = (bottom + top + 1) / 2;
        if (matrix[mid][0] <= target) {
            top = mid;
        } else {
            bottom = mid - 1;
        }
    }
    
    // 在目标行中二分查找
    int row = top;
    int left = 0, right = n - 1;
    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;
}

🎯 相关题目引申 ​

  1. 搜索二维矩阵 II（LeetCode 240）

    • 类似但矩阵只保证行列有序
    • 需要不同的搜索策略

  2. 有序矩阵中的第k小元素（LeetCode 378）

    • 利用类似的矩阵性质
    • 但需要结合二分查找和计数

🌟 面试常见追问 ​

  1. 如何处理重复元素？

    • 当前题目不涉及重复元素
    • 但可以考虑查找第一个/最后一个位置

  2. 能否优化空间复杂度？

    • 当前方案已经是O(1)空间复杂度
    • 主要优化点在于减少不必要的计算

  3. 如果矩阵很大，如何优化？

    • 考虑分块处理
    • 可以使用并行计算

作者：忍者算法 公众号：忍者算法

🎁 回复【刷题清单】获取LeetCode高频面试题合集 🧑‍💻 回复【代码】获取多语言完整题解 💡 回复【加群】加入算法交流群，一起进步

#算法面试 #LeetCode #二分查找 #矩阵搜索