欢迎来到李耶的频道【LeetCode面试题】。搜索二维矩阵 II240.搜索二维矩阵 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.lengthn matrix[i].length1 n, m 300-10^9 matrix[i][j] 10^9每行的所有元素从左到右升序排列每列的所有元素从上到下升序排列-10^9 target 10^9解法一Z 字形查找从右上角开始⭐思路从矩阵的右上角开始搜索。利用矩阵每行从左到右递增、每列从上到下递增的特性像走迷宫一样排除行或列如果当前值大于目标值说明当前列的所有元素都大于目标值向左移动一列如果当前值小于目标值说明当前行的所有元素都小于目标值向下移动一行。functionsearchMatrix(matrix,target){if(!matrix||matrix.length0||matrix[0].length0)returnfalse;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)优势充分利用矩阵特性每次排除一行或一列效率高是面试中最推荐的写法解法二Z 字形查找从左下角开始思路从左下角开始搜索。如果当前值大于目标值向上移动一行如果当前值小于目标值向右移动一列。原理与从右上角开始相同只是方向相反。functionsearchMatrix(matrix,target){if(!matrix||matrix.length0||matrix[0].length0)returnfalse;constmmatrix.length;constnmatrix[0].length;letrowm-1;letcol0;while(row0coln){constvalmatrix[row][col];if(valtarget)returntrue;if(valtarget){col;}else{row--;}}returnfalse;}时间复杂度 / 空间复杂度O(m n) / O(1)优势与从右上角开始本质相同可作为备选写法解法三逐行二分查找思路对每一行使用二分查找利用每行升序的特性。虽然每列升序的特性没有被充分利用但实现简单。functionsearchMatrix(matrix,target){for(constrowofmatrix){letleft0;letrightrow.length-1;while(leftright){constmidMath.floor(left(right-left)/2);if(row[mid]target)returntrue;if(row[mid]target){leftmid1;}else{rightmid-1;}}}returnfalse;}时间复杂度 / 空间复杂度O(m·log n) / O(1)优势代码直观易于理解作为补充解法展示劣势时间复杂度高于 Z 字形查找解法对比解法时间 / 空间复杂度优势推荐指数Z 字形查找右上角O(mn) / O(1)充分利用矩阵特性最优解法⭐⭐⭐⭐⭐Z 字形查找左下角O(mn) / O(1)与右上角等价方向不同⭐⭐⭐⭐⭐逐行二分查找O(m·log n) / O(1)实现简单易于理解⭐⭐⭐与 LeetCode 74 题的区别特性74. 搜索二维矩阵240. 搜索二维矩阵 II每行升序✅✅每列升序✅由行首 前行末隐含推出✅显式给出行首 前行末✅❌无此约束整体有序✅展开为一维升序❌最优解法二分查找 O(log(m·n))Z 字形查找 O(mn)扩展题搜索二维矩阵与本题类似但矩阵具有每行第一个整数大于前一行的最后一个整数的特性整体有序可用二分查找。搜索插入位置在有序数组中查找目标值的插入位置。搜索旋转排序数组在旋转排序数组中搜索目标值要求 O(log n) 时间复杂度。“见微以知萌见端以知末。” —— 韩非子关注李耶每天一道面试题一起卷起来
