【LeetCode】74.搜索二维矩阵

欢迎来到李耶的频道【LeetCode面试题】。

---

搜索二维矩阵

74.搜索二维矩阵

题目

编写一个高效的算法来判断m x n矩阵中，是否存在一个目标值。该矩阵具有如下特性：

• 每行中的整数从左到右按升序排列。
• 每行的第一个整数大于前一行的最后一个整数。

也就是说，整个矩阵按行展开后是一个升序的一维数组。

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

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13 输出：false

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 100
• -10^4 <= matrix[i][j], target <= 10^4

解法一：二维转一维二分查找（推荐）⭐

思路：将m x n矩阵视为一个长度为m * n的升序一维数组，直接用二分查找即可。关键在于坐标转换：一维下标mid对应矩阵的(mid / n, mid % n)位置。

functionsearchMatrix(matrix,target){constm=matrix.length;constn=matrix[0].length;letleft=0;letright=m*n-1;while(left<=right){constmid=Math.floor(left+(right-left)/2);// 一维下标转二维坐标constrow=Math.floor(mid/n);constcol=mid%n;constval=matrix[row][col];if(val===target)returntrue;if(val<target){left=mid+1;}else{right=mid-1;}}returnfalse;}

• 时间复杂度 / 空间复杂度：O(log(m·n)) / O(1)
• 优势：代码极简，利用矩阵的"整体有序"特性，面试中最推荐的写法

解法二：两次二分（先列后行）

思路：先对第一列进行二分查找，找到目标值所在的行（最后一个matrix[row][0] <= target的行），再在该行进行标准二分查找。

functionsearchMatrix(matrix,target){constm=matrix.length;constn=matrix[0].length;// 1. 在第一列中二分，找到最后一个 <= target 的行lettop=0;letbottom=m-1;while(top<=bottom){constmid=Math.floor(top+(bottom-top)/2);if(matrix[mid][0]===target)returntrue;if(matrix[mid][0]<target){top=mid+1;}else{bottom=mid-1;}}// 目标行就是 bottom（即第一个列值 > target 的上一行）constrow=bottom;if(row<0)returnfalse;// 2. 在目标行中进行二分查找letleft=0;letright=n-1;while(left<=right){constmid=Math.floor(left+(right-left)/2);if(matrix[row][mid]===target)returntrue;if(matrix[row][mid]<target){left=mid+1;}else{right=mid-1;}}returnfalse;}

• 时间复杂度 / 空间复杂度：O(log m + log n) / O(1)
• 优势：分步逻辑清晰，不需要坐标转换，易于理解

解法三：从右上角开始"Z 字形"搜索

思路：从矩阵右上角开始，利用矩阵每行从左到右、每列从上到下递增的特性，像走迷宫一样移动指针，每次排除一行或一列。

functionsearchMatrix(matrix,target){constm=matrix.length;constn=matrix[0].length;letrow=0;letcol=n-1;while(row<m&&col>=0){constval=matrix[row][col];if(val===target)returntrue;if(val<target){row++;// 当前值小于目标，向下移（行增大）}else{col--;// 当前值大于目标，向左移（列减小）}}returnfalse;}

• 时间复杂度 / 空间复杂度：O(m + n) / O(1)
• 优势：利用矩阵特性，无需二分，思维独特
• 劣势：时间复杂度略高于二分法，可作为补充解法展示

解法对比

解法	时间 / 空间复杂度	优势	推荐指数
一维转二维二分	O(log(m·n)) / O(1)	代码最简，全局有序	⭐⭐⭐⭐⭐
两次二分	O(log m + log n) / O(1)	分步清晰，无需坐标转换	⭐⭐⭐⭐
Z 字形搜索	O(m + n) / O(1)	思维独特，可扩展到 240 题	⭐⭐⭐⭐

与 LeetCode 240 题的区别

本题的进阶版本是240. 搜索二维矩阵 II，两题的核心区别如下：

特性	74. 搜索二维矩阵	240. 搜索二维矩阵 II
每行升序	✅	✅
每列升序	✅（由行首大于前行末隐含推出）	✅（显式给出）
行首 > 前行末	✅	❌（无此约束）
整体有序	✅（展开为一维升序）	❌（展开后不一定有序）
最优解法	二分查找 O(log(m·n))	Z 字形搜索 O(m+n)

扩展题

1. 搜索二维矩阵 II：与本题类似，但矩阵每行每列分别升序，且行首不一定大于前行末，要求高效搜索。
2. 搜索插入位置：在有序数组中查找目标值的插入位置。
3. 在排序数组中查找元素的第一个和最后一个位置：在有序数组中查找目标值的左右边界。

---

“见微以知萌，见端以知末。” —— 韩非子

关注李耶，每天一道面试题，一起卷起来 🔥