LeetCode 74. 搜索二维矩阵：两种高效解题思路

在LeetCode的数组类题目中「搜索二维矩阵」是一道经典的二分查找应用题核心考察对有序结构的利用和二分思想的灵活运用。题目给出的矩阵有两个关键特性每行从左到右非严格递增且每行第一个元素大于前一行最后一个元素。这两个特性决定了我们可以用高效的二分查找替代暴力遍历将时间复杂度从O(mn)优化到O(log(mn))或O(logm logn)。今天就来拆解这道题的两种主流解题方法结合代码逐行解析帮大家理清思路、吃透细节无论是面试还是日常刷题都能轻松应对。题目回顾给定一个m x n的整数矩阵满足每行中的整数从左到右按非严格递增顺序排列。每行的第一个整数大于前一行的最后一个整数。给定一个整数target判断target是否在矩阵中存在返回true否则返回false。示例若矩阵为[[1,3,5,7],[10,11,16,20],[23,30,34,60]]target3则返回truetarget13则返回false。思路一将二维矩阵“扁平化”为一维数组最优解观察题目给出的矩阵特性我们会发现一个关键整个矩阵可以看作是一个“有序的一维数组”。因为每行递增且下一行的第一个元素大于上一行最后一个相当于把所有行拼接起来就是一个严格递增的一维数组。基于这个特性我们可以直接对这个“虚拟的一维数组”做二分查找无需额外处理行和列的关系只需要将一维数组的索引与二维矩阵的行、列做映射即可。代码实现TypeScriptfunctionsearchMatrix_1(matrix:number[][],target:number):boolean{// 边界判断矩阵为空或第一行为空直接返回falseif(!matrix||!matrix[0]){returnfalse;}constmmatrix.length;// 矩阵的行数constnmatrix[0].length;// 矩阵的列数letlow0,highm*n-1;// 虚拟一维数组的左右边界索引从0到m*n-1// 二分查找核心逻辑while(lowhigh){letmidMath.floor((highlow)/2);// 中间索引一维数组// 关键将一维索引mid映射到二维矩阵的行和列// 行索引 Math.floor(mid / n)相当于mid除以列数取整// 列索引 mid % n相当于mid除以列数取余letxmatrix[Math.floor(mid/n)][mid%n];if(xtarget){// 目标值在右半部分缩小左边界lowmid1;}elseif(xtarget){// 目标值在左半部分缩小右边界highmid-1;}else{// 找到目标值直接返回truereturntrue;}}// 循环结束仍未找到返回falsereturnfalse;};核心细节解析边界处理首先判断矩阵是否为空matrix为null/undefined或第一行是否为空matrix[0]为空这两种情况直接返回false避免后续索引越界。索引映射这是该思路的核心。假设虚拟一维数组的索引为mid那么对应的二维矩阵行索引是Math.floor(mid / n)因为每一行有n个元素每n个索引对应一行列索引是mid % n取余得到当前行内的位置。时间复杂度O(log(mn))因为二分查找的次数是log2(mn)每次查找仅做一次索引映射和数值比较时间为O(1)。空间复杂度O(1)仅使用了几个变量存储边界和中间值没有额外开辟空间。思路二两次二分查找先找行再找列如果觉得“扁平化”的索引映射不好理解还可以采用更直观的两次二分查找第一步先找到target可能所在的行第二步在该行中查找target是否存在。第一步找行遍历矩阵的行首元素找到“最后一个行首元素 ≤ target”的行因为矩阵每行递增且下一行首元素大于上一行尾元素target如果存在一定在这一行。第二步找列在找到的目标行中用二分查找判断target是否存在。代码实现TypeScriptfunctionsearchMatrix_2(matrix:number[][],target:number):boolean{// 边界判断矩阵为空或第一行为空直接返回falseif(!matrix||!matrix[0]){returnfalse;}constmmatrix.length;constnmatrix[0].length;// 第一步二分查找目标行返回target可能所在的行索引找不到返回-1constsearchRow():number{letlow0,highm-1;lettargetRow-1;// 初始化目标行为-1表示未找到while(lowhigh){constmidMath.floor((highlow)/2);if(matrix[mid][0]target){// 当前行首元素 ≤ target可能是目标行继续向右查找更合适的行lowmid1;targetRowmid;// 更新目标行}elseif(matrix[mid][0]target){// 当前行首元素 target目标行在左半部分highmid-1;}}returntargetRow;}constrowsearchRow();if(row-1){// 没有找到符合条件的行直接返回falsereturnfalse;}// 第二步在目标行中二分查找targetconstsearchCol():boolean{letlow0,highn-1;while(lowhigh){constmidMath.floor((lowhigh)/2);if(matrix[row][mid]target){lowmid1;}elseif(matrix[row][mid]target){highmid-1;}else{returntrue;}}returnfalse;}returnsearchCol();};核心细节解析找行逻辑searchRow函数中我们始终记录“最后一个行首元素 ≤ target”的行因为如果target存在必然在这一行下一行的行首元素大于target不可能在下行。如果循环结束后targetRow仍为-1说明所有行首元素都大于targettarget不存在。找列逻辑searchCol函数就是标准的一维数组二分查找在目标行中遍历列判断target是否存在。时间复杂度O(logm logn)两次二分查找分别消耗O(logm)和O(logn)整体与思路一的O(log(mn))等价因为log(mn) logm logn。空间复杂度O(1)同样没有额外开辟空间仅使用局部变量。两种思路对比与总结思路核心逻辑时间复杂度空间复杂度特点思路一扁平化将矩阵看作一维数组一次二分查找O(log(mn))O(1)代码简洁索引映射是关键稍难理解思路二两次二分先找行再找列两次二分查找O(logm logn)O(1)逻辑直观分步清晰容易理解解题关键总结这道题的核心是利用矩阵的“有序性”——无论是将其扁平化看作一维有序数组还是分两步找行、找列本质都是二分查找思想的应用。解题时需要注意两个关键点边界处理必须先判断矩阵是否为空、行是否为空避免索引越界。索引映射思路一/ 行判断思路二这是两种思路的核心也是容易出错的地方需要熟练掌握。