企业官网建设流程全解析

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

搜索二维矩阵 II

240.搜索二维矩阵 II

题目

编写一个高效的算法来搜索m x n矩阵matrix中的一个目标值target。该矩阵具有以下特性：

• 每行的元素从左到右升序排列。
• 每列的元素从上到下升序排列。

输入：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 输出：true

输入：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 = 20 输出：false

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= n, m <= 300
• -10^9 <= matrix[i][j] <= 10^9
• 每行的所有元素从左到右升序排列
• 每列的所有元素从上到下升序排列
• -10^9 <= target <= 10^9

解法一：Z 字形查找（从右上角开始）⭐

思路：从矩阵的右上角开始搜索。利用矩阵每行从左到右递增、每列从上到下递增的特性，像走迷宫一样排除行或列：如果当前值大于目标值，说明当前列的所有元素都大于目标值，向左移动一列；如果当前值小于目标值，说明当前行的所有元素都小于目标值，向下移动一行。

functionsearchMatrix(matrix,target){if(!matrix||matrix.length===0||matrix[0].length===0)returnfalse;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)
• 优势：充分利用矩阵特性，每次排除一行或一列，效率高，是面试中最推荐的写法

解法二：Z 字形查找（从左下角开始）

思路：从左下角开始搜索。如果当前值大于目标值，向上移动一行；如果当前值小于目标值，向右移动一列。原理与从右上角开始相同，只是方向相反。

functionsearchMatrix(matrix,target){if(!matrix||matrix.length===0||matrix[0].length===0)returnfalse;constm=matrix.length;constn=matrix[0].length;letrow=m-1;letcol=0;while(row>=0&&col<n){constval=matrix[row][col];if(val===target)returntrue;if(val<target){col++;}else{row--;}}returnfalse;}

• 时间复杂度 / 空间复杂度：O(m + n) / O(1)
• 优势：与从右上角开始本质相同，可作为备选写法

解法三：逐行二分查找

思路：对每一行使用二分查找，利用每行升序的特性。虽然每列升序的特性没有被充分利用，但实现简单。

functionsearchMatrix(matrix,target){for(constrowofmatrix){letleft=0;letright=row.length-1;while(left<=right){constmid=Math.floor(left+(right-left)/2);if(row[mid]===target)returntrue;if(row[mid]<target){left=mid+1;}else{right=mid-1;}}}returnfalse;}

• 时间复杂度 / 空间复杂度：O(m·log n) / O(1)
• 优势：代码直观，易于理解，作为补充解法展示
• 劣势：时间复杂度高于 Z 字形查找

解法对比

与 LeetCode 74 题的区别

扩展题

1. 搜索二维矩阵：与本题类似，但矩阵具有"每行第一个整数大于前一行的最后一个整数"的特性，整体有序，可用二分查找。
2. 搜索插入位置：在有序数组中查找目标值的插入位置。
3. 搜索旋转排序数组：在旋转排序数组中搜索目标值，要求 O(log n) 时间复杂度。

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

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