240.搜索二维矩阵Ⅱ

题目描述题解一(直接查找)直接遍历整个矩阵 matrix判断 target 是否出现即可代码classSolution{publicbooleansearchMatrix(int[][]matrix,inttarget){for(int[]row:matrix){for(intelement:row){if(elementtarget){returntrue;}}}returnfalse;}}复杂度分析时间复杂度O(mn)空间复杂度O(1)题解二(Z 字形查找)(最推荐)思路可以将矩阵逆时针旋转45°,理解为二叉搜索树(左节点根节点右节点)leetcode用户Krahets的理解代码classSolution{publicbooleansearchMatrix(int[][]matrix,inttarget){// 处理边界情况虽然题目提示中说 n, m 1但加上防御性编程是个好习惯if(matrixnull||matrix.length0||matrix[0].length0){returnfalse;}intmmatrix.length;intnmatrix[0].length;// 初始化指针指向右上角的元素introw0;intcoln-1;// 当指针没有越界时继续搜索while(rowmcol0){if(matrix[row][col]target){returntrue;// 找到了目标值}elseif(matrix[row][col]target){col--;// 当前值偏大向左移动剔除当前列}else{row;// 当前值偏小向下移动剔除当前行}}// 遍历完如果没有找到返回 falsereturnfalse;}}复杂度分析时间复杂度O(mn)O(m n)O(mn)。其中mmm是矩阵的行数nnn是矩阵的列数。在最坏的情况下目标值在左下角或不存在我们需要向下移动mmm次向左移动nnn次所以总的时间复杂度为O(mn)O(m n)O(mn)。这比直接遍历整个矩阵的O(m×n)O(m \times n)O(m×n)要高效得多空间复杂度O(1)O(1)O(1)。算法只使用了常数级别的额外空间几个整型变量来记录行号和列号题解三(逐行二分查找 剪枝)思路题目明确说明了“每行的元素从左到右升序排列”这就完全满足了使用二分查找的前提条件代码classSolution{publicbooleansearchMatrix(int[][]matrix,inttarget){//判空防御if(matrixnull||matrix.length0||matrix[0].length0){returnfalse;}intmmatrix.length;intnmatrix[0].length;for(inti0;im;i){// 剪枝 1如果当前行第一个元素已经大于 target后面的行更不可能有直接结束if(matrix[i][0]target){break;}//剪枝 2如果当前行最后一个元素小于 target说明肯定不在这一行看下一行if(matrix[i][n-1]target){continue;}//对当前行进行二分查找if(binarySearch(matrix[i],target)){returntrue;}}returnfalse;}// 标准的二分查找辅助方法privatebooleanbinarySearch(int[]arr,inttarget){intleft0;intrightarr.length-1;while(leftright){intmidleft(right-left)/2;if(targetarr[mid]){rightmid-1;}elseif(targetarr[mid]){leftmid1;}else{returntrue;}}returnfalse;}}复杂度分析时间复杂度O(mlog⁡n)O(m \log n)O(mlogn)。其中mmm是矩阵的行数nnn是矩阵的列数。我们需要遍历最多mmm行每行进行二分查找的时间复杂度是O(log⁡n)O(\log n)O(logn)(补充说明如果矩阵是一个“扁平”的矩形即行数mmm远小于列数nnn时O(mlog⁡n)O(m \log n)O(mlogn)甚至会比前面的O(mn)O(m n)O(mn)还要快)空间复杂度O(1)O(1)O(1)。只使用了常数级别的额外空间来记录双指针 left、right 和 mid 等