LeetCode 74：搜索二维矩阵——Java 虚拟一维数组与二分查找详解

一、题目描述给定一个m × n的整数矩阵matrix矩阵具有以下两个特点每一行中的整数从左到右按非严格递增顺序排列每一行的第一个整数都大于前一行的最后一个整数。再给定一个整数target如果它存在于矩阵中就返回true否则返回false。例如matrix [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60] ] target 3数字3位于第一行第二列因此返回true。如果target 13矩阵中不存在该数字则返回false。看到“有序”和“查找”这两个关键词应该优先想到二分查找。本题的关键在于如何在不创建额外数组的情况下对二维矩阵进行一次二分查找。二、为什么可以把矩阵看成一维数组先观察题目给出的矩阵1 3 5 7 10 11 16 20 23 30 34 60每一行内部都是升序的并且下一行的第一个数字大于上一行的最后一个数字。因此如果按照从左到右、从上到下的顺序展开可以得到[1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60]这个一维数组仍然保持整体升序所以可以直接使用二分查找。最直观的做法是创建一个新数组将矩阵中的所有元素复制进去再对新数组进行搜索。但这会额外占用O(mn)的空间而且复制数据本身也需要O(mn)的时间。实际上我们不需要真正展开矩阵。只要能够把一维数组的下标映射回矩阵中的行和列就可以把原矩阵当成一个“虚拟的一维数组”。三、一维下标如何映射到二维坐标假设矩阵有n列。一维数组中的每n个元素对应二维矩阵中的一整行。如果一个元素在虚拟一维数组中的下标为i那么它在二维矩阵中的坐标为行号 i / n 列号 i % n这里使用的都是整数运算。以三行四列的矩阵为例n 4一维下标1行号为1 / 4 0列号为1 % 4 1对应matrix[0][1] 3一维下标6行号为6 / 4 1列号为6 % 4 2对应matrix[1][2] 16一维下标9行号为9 / 4 2列号为9 % 4 1对应matrix[2][1] 30。因此在二分查找中得到中间下标mid后可以直接通过下面的代码访问对应元素int num matrix[mid / n][mid % n];这就是本题最核心的下标映射关系。可以简单记忆为除以列数得到行模上列数得到列。四、确定二分查找的边界矩阵一共有m行、n列因此元素总数是m × n。如果按照虚拟一维数组处理其下标范围就是0 m × n - 1所以二分查找的左右边界为int left 0; int right m * n - 1;这里采用闭区间[left, right]。只要left right区间内就仍然存在尚未检查的元素while (left right) { // 二分查找 }为了避免直接计算(left right) / 2时发生整数溢出可以写成int mid left ((right - left) 1);在本题的数据范围内截图中的(left right) 1通常也能通过。但从通用二分查找模板来看先计算right - left更稳妥。五、如何更新左右边界通过映射关系取得中间元素后将它与target比较int num matrix[mid / n][mid % n];接下来有三种情况。1. 中间元素等于目标值if (num target) { return true; }说明已经找到目标值可以直接结束搜索。2. 中间元素小于目标值if (num target) { left mid 1; }因为虚拟数组整体有序所以mid及其左侧的元素都不可能等于target下一轮只需要搜索右半部分。3. 中间元素大于目标值else { right mid - 1; }此时mid及其右侧的元素都可以排除下一轮只搜索左半部分。如果循环结束后仍未返回true说明目标值不存在最终返回false。六、完整 Java 代码class Solution { public boolean searchMatrix(int[][] matrix, int target) { 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) 1); // 将一维下标映射回二维矩阵坐标 int num matrix[mid / n][mid % n]; if (num target) { return true; } if (num target) { left mid 1; } else { right mid - 1; } } return false; } }这段代码没有真正创建一维数组只是在逻辑上将二维矩阵展开。二分查找使用的是虚拟下标只有访问元素时才通过除法和取模转换为二维坐标。七、示例推演仍以如下输入为例matrix [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60] ] target 3矩阵共有3 × 4 12个元素因此初始搜索区间为[0, 11]。第一次查找mid 5 row 5 / 4 1 col 5 % 4 1 num matrix[1][1] 11因为11 3所以令right 4。第二次查找mid 2 row 2 / 4 0 col 2 % 4 2 num matrix[0][2] 5因为5 3所以令right 1。第三次查找mid 0 num matrix[0][0] 1因为1 3所以令left 1。第四次查找mid 1 num matrix[0][1] 3中间元素等于目标值返回true。八、复杂度分析矩阵中共有m × n个元素二分查找每次都将搜索范围缩小一半因此时间复杂度为O(log(m × n))算法只使用了几个变量没有创建真正的一维数组因此空间复杂度为O(1)九、常见错误1. 使用mid / m计算行号映射时应该除以列数n因为一维数组中每连续n个元素构成一行。正确写法是matrix[mid / n][mid % n]2. 将右边界写成m * n一共有m × n个元素但最后一个下标是m × n - 1。闭区间写法中右边界应为int right m * n - 1;3. 更新边界时没有跳过mid如果写成left mid或right mid在某些情况下区间无法继续缩小可能造成死循环。闭区间模板应使用mid 1和mid - 1。4. 忽略矩阵整体有序的前提这种虚拟展开后二分查找的方法成立是因为下一行首元素大于上一行尾元素。如果只保证每行有序而不能保证行与行之间整体有序就不能直接使用本方法。5. 真的创建一维数组创建数组虽然也能完成搜索但会带来O(mn)的复制时间和额外空间失去了虚拟映射的优势。十、总结这道题本质上仍然是一道标准二分查找题。矩阵看起来是二维结构但题目给出的两条有序条件保证了它按行展开后是一个完整的升序数组。我们不需要真正展开矩阵只需在[0, m × n - 1]范围内进行二分查找。当得到一维下标mid后利用mid / n找到行号利用mid % n找到列号再访问对应的矩阵元素。