欢迎来到李耶的频道【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.lengthn matrix[i].length1 m, n 100-10^4 matrix[i][j], target 10^4解法一二维转一维二分查找推荐⭐思路将m x n矩阵视为一个长度为m * n的升序一维数组直接用二分查找即可。关键在于坐标转换一维下标mid对应矩阵的(mid / n, mid % n)位置。functionsearchMatrix(matrix,target){constmmatrix.length;constnmatrix[0].length;letleft0;letrightm*n-1;while(leftright){constmidMath.floor(left(right-left)/2);// 一维下标转二维坐标constrowMath.floor(mid/n);constcolmid%n;constvalmatrix[row][col];if(valtarget)returntrue;if(valtarget){leftmid1;}else{rightmid-1;}}returnfalse;}时间复杂度 / 空间复杂度O(log(m·n)) / O(1)优势代码极简利用矩阵的整体有序特性面试中最推荐的写法解法二两次二分先列后行思路先对第一列进行二分查找找到目标值所在的行最后一个matrix[row][0] target的行再在该行进行标准二分查找。functionsearchMatrix(matrix,target){constmmatrix.length;constnmatrix[0].length;// 1. 在第一列中二分找到最后一个 target 的行lettop0;letbottomm-1;while(topbottom){constmidMath.floor(top(bottom-top)/2);if(matrix[mid][0]target)returntrue;if(matrix[mid][0]target){topmid1;}else{bottommid-1;}}// 目标行就是 bottom即第一个列值 target 的上一行constrowbottom;if(row0)returnfalse;// 2. 在目标行中进行二分查找letleft0;letrightn-1;while(leftright){constmidMath.floor(left(right-left)/2);if(matrix[row][mid]target)returntrue;if(matrix[row][mid]target){leftmid1;}else{rightmid-1;}}returnfalse;}时间复杂度 / 空间复杂度O(log m log n) / O(1)优势分步逻辑清晰不需要坐标转换易于理解解法三从右上角开始Z 字形搜索思路从矩阵右上角开始利用矩阵每行从左到右、每列从上到下递增的特性像走迷宫一样移动指针每次排除一行或一列。functionsearchMatrix(matrix,target){constmmatrix.length;constnmatrix[0].length;letrow0;letcoln-1;while(rowmcol0){constvalmatrix[row][col];if(valtarget)returntrue;if(valtarget){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(mn)扩展题搜索二维矩阵 II与本题类似但矩阵每行每列分别升序且行首不一定大于前行末要求高效搜索。搜索插入位置在有序数组中查找目标值的插入位置。在排序数组中查找元素的第一个和最后一个位置在有序数组中查找目标值的左右边界。“见微以知萌见端以知末。” —— 韩非子关注李耶每天一道面试题一起卷起来 【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.lengthn matrix[i].length1 m, n 100-10^4 matrix[i][j], target 10^4解法一二维转一维二分查找推荐⭐思路将m x n矩阵视为一个长度为m * n的升序一维数组直接用二分查找即可。关键在于坐标转换一维下标mid对应矩阵的(mid / n, mid % n)位置。functionsearchMatrix(matrix,target){constmmatrix.length;constnmatrix[0].length;letleft0;letrightm*n-1;while(leftright){constmidMath.floor(left(right-left)/2);// 一维下标转二维坐标constrowMath.floor(mid/n);constcolmid%n;constvalmatrix[row][col];if(valtarget)returntrue;if(valtarget){leftmid1;}else{rightmid-1;}}returnfalse;}时间复杂度 / 空间复杂度O(log(m·n)) / O(1)优势代码极简利用矩阵的整体有序特性面试中最推荐的写法解法二两次二分先列后行思路先对第一列进行二分查找找到目标值所在的行最后一个matrix[row][0] target的行再在该行进行标准二分查找。functionsearchMatrix(matrix,target){constmmatrix.length;constnmatrix[0].length;// 1. 在第一列中二分找到最后一个 target 的行lettop0;letbottomm-1;while(topbottom){constmidMath.floor(top(bottom-top)/2);if(matrix[mid][0]target)returntrue;if(matrix[mid][0]target){topmid1;}else{bottommid-1;}}// 目标行就是 bottom即第一个列值 target 的上一行constrowbottom;if(row0)returnfalse;// 2. 在目标行中进行二分查找letleft0;letrightn-1;while(leftright){constmidMath.floor(left(right-left)/2);if(matrix[row][mid]target)returntrue;if(matrix[row][mid]target){leftmid1;}else{rightmid-1;}}returnfalse;}时间复杂度 / 空间复杂度O(log m log n) / O(1)优势分步逻辑清晰不需要坐标转换易于理解解法三从右上角开始Z 字形搜索思路从矩阵右上角开始利用矩阵每行从左到右、每列从上到下递增的特性像走迷宫一样移动指针每次排除一行或一列。functionsearchMatrix(matrix,target){constmmatrix.length;constnmatrix[0].length;letrow0;letcoln-1;while(rowmcol0){constvalmatrix[row][col];if(valtarget)returntrue;if(valtarget){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(mn)扩展题搜索二维矩阵 II与本题类似但矩阵每行每列分别升序且行首不一定大于前行末要求高效搜索。搜索插入位置在有序数组中查找目标值的插入位置。在排序数组中查找元素的第一个和最后一个位置在有序数组中查找目标值的左右边界。“见微以知萌见端以知末。” —— 韩非子关注李耶每天一道面试题一起卷起来