74.搜索二维矩阵

题目描述非严格递增:允许出现重复元素的递增序列。也就是说后面的数字可以大于前面的数字也可以等于前面的数字但绝对不能小于前面的数字题解一(一次二分查找)(推荐,不容易出错且复杂度与题解二相同)思路代码classSolution{publicbooleansearchMatrix(int[][]matrix,inttarget){// 处理边界情况if(matrixnull||matrix.length0||matrix[0].length0){returnfalse;}intmmatrix.length;intnmatrix[0].length;// 将二维矩阵看作一维数组进行二分查找intleft0;intrightm*n-1;while(leftright){intmidleft(right-left)/2;// 将一维索引转换为二维矩阵的行和列introwmid/n;intcolmid%n;intmidValuematrix[row][col];if(midValuetarget){returntrue;}elseif(midValuetarget){leftmid1;// 目标值在右半部分}else{rightmid-1;// 目标值在左半部分}}returnfalse;}}复杂度分析时间复杂度:O(log⁡(mn))O(\log(mn))O(log(mn))。其中mmm和nnn分别是矩阵的行数和列数空间复杂度:O(1)O(1)O(1)。只使用了常数级别的额外空间来存储指针和坐标变量题解二(两次二分查找)(当作练习“寻找下界/上界”的模板来彻底吃透对以后解决更复杂的二分变体题会非常有帮助)思路代码classSolution{publicbooleansearchMatrix(int[][]matrix,inttarget){// 第一步在第一列中二分查找找到目标可能存在的那一行introwIndexbinarySearchFirstColumn(matrix,target);// 如果返回的行索引小于0说明 target 比矩阵左上角的最小元素还要小直接返回 falseif(rowIndex0){returnfalse;}// 第二步在确定的那一行中进行标准的二分查找寻找 targetreturnbinarySearchRow(matrix[rowIndex],target);}//核心难点这个方法的目的是找到最后一个首元素小于或等于 target 的行////解析1:binarySearchFirstColumn方法中几个特殊技巧//publicintbinarySearchFirstColumn(int[][]matrix,inttarget){// 技巧1low 初始化为 -1intlow-1,highmatrix.length-1;while(lowhigh){// 技巧2计算 mid 时加 1实现“向上取整”intmid(high-low1)/2low;if(matrix[mid][0]target){// 如果当前行的首元素 target说明目标值可能在当前行或者更下面的行// 所以 low 更新为 mid 注意这里保留了 midlowmid;}else{// 如果当前行的首元素 target说明目标值只可能在上面的行highmid-1;}}returnlow;}//标准二分查找publicbooleanbinarySearchRow(int[]row,inttarget){intlow0,highrow.length-1;// 标准的 判断while(lowhigh){// 标准的向下取整防溢出写法intmid(high-low)/2low;if(row[mid]target){returntrue;// 找到了}elseif(row[mid]target){highmid-1;// 目标在左边}else{lowmid1;// 目标在右边}}returnfalse;// 找遍了也没找到}}解析1:binarySearchFirstColumn方法中几个特殊技巧复杂度分析时间复杂度:O(log⁡(mn))O(\log(mn))O(log(mn))。其中mmm和nnn分别是矩阵的行数和列数空间复杂度O(1)O(1)O(1)。仅仅在栈空间里声明了几个基本类型的整型变量比如 low, high, mid, rowIndex