网站浮动条,坪山新区城市建设局网站,深圳门户网站建设公司,最新新闻热点事件短篇文章目录题目描述题解一 无脑暴力循环题解二 初始二分法#x1f315;博客x主页#xff1a;己不由心王道长#x1f315;! #x1f30e;文章说明#xff1a;剑指offer-二维数组中的查找#x1f30e; ✅系列专栏#xff1a;剑指offer #x1f334;本篇内容#xff1a;对剑…
文章目录题目描述题解一 无脑暴力循环题解二 初始二分法博客x主页己不由心王道长! 文章说明剑指offer-二维数组中的查找 ✅系列专栏剑指offer 本篇内容对剑指offer中的数组进行学习和解析 ☕️每日一语这个世界本来就不完美如果我们再不接受不完美的自己那我们要怎么活。☕️ 交流社区己不由心王道长(优质编程社区) 题目描述 在一个 n * m 的二维数组中每一行都按照从左到右 非递减 的顺序排序每一列都按照从上到下 非递减 的顺序排序。请完成一个高效的函数输入这样的一个二维数组和一个整数判断数组中是否含有该整数。
示例:
现有矩阵 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。
给定 target 20返回 false。
限制
0 n 1000
0 m 1000
题解一 无脑暴力循环
思路 由于题目给出的是一个n * m 的二维数组不考虑其他因素只要判断数组里面有没有目标元素而言直接双层for循环暴力解决代码如下
class Solution {public boolean findNumberIn2DArray(int[][] matrix, int target) {for(int i0;imatrix.length;i){for(int j 0;jmatrix[i].length;j){if(matrix[i][j]target){return true;}}}return false;}
}结果: 想法确实无脑暴力可解但是这里的执行用时感觉不对劲两层for循环时间复杂度O(n*m),应该不算快才对。
题解二 初始二分法
思路 如图所示题目给出的是没一行都按照从左到右非递减的顺序排列就是说其实这个数组在一维的角度来说是有顺序的当然二维也有仔细观察就能发现————用处就是我们的二分法在应用的时候就需要有顺序的数组明白了吗 先看代码
class Solution {public boolean findNumberIn2DArray(int[][] matrix, int target) {for(int i 0;imatrix.length;i){int left0;//在while循环外侧设置当while循环结束后可以重新给left和right赋值int rightmatrix[0].length-1;//开始是在matrix[0][x]使用二分法就是每一行使用二分一行结束之后换到下一行while(leftright){int middle left((right-left)/2);if(matrix[i][middle]target){return true;}else if(targetmatrix[i][middle]){//目标小向左查找rightmiddle-1;}else{left middle1;}}}return false;}
}这里在每一行上都使用了二分法就是在每次for循环在循环行的时候对行进行二分法。 结果
