LeetCode中如何查找二维数组查找
LeetCode中如何查找二维数组查找,针对这个问题,这篇文章详细介绍了相对应的分析和解答,希望可以帮助更多想解决这个问题的小伙伴找到更简单易行的方法。
创新互联在网站设计、网站制作、成都app软件开发、网站运营等方面均有出色的表现,凭借多年丰富的经验,我们会仔细了解各客户的需求而做出多方面的分析、设计、整合,为客户设计出具风格及创意性的商业解决方案,我们更提供一系列网络营销推广,网站制作和网站推广的服务,以推动各中小企业全面信息化,并利用创新技术帮助各行业提升企业形象和运营效率。
二维数组中的查找
在一个 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
解法一
题目理解起来很简单,一个二维数组,一个数字。判断数组里面有没有这个数字。
另外还有一个提干是每一行每一列都是数字递增,待会再看看这个题干怎么利用起来。
如果只是一个数组里面找数字,那么很容易想到的就是直接遍历。
class Solution { public boolean findNumberIn2DArray(int[][] matrix, int target) { if (matrix == null || matrix.length == 0 || matrix[0].length == 0) { return false; } int rows = matrix.length, columns = matrix[0].length; for (int i = 0; i < rows; i++) { for (int j = 0; j < columns; j++) { if (matrix[i][j] == target) { return true; } } } return false; } }
方法消耗情况
执行用时:0-1 ms 内存消耗:44.3 MB
时间复杂度
由于用到了二维数组的遍历,所以时间复杂度就是O(mn),用到了时间复杂度的乘法计算。
空间复杂度
除了本身的数组,只用到了几个变量,所以空间复杂度是O(1)。
解法二
接下来我们就看看怎么利用刚才说到的数字递增题干,得出新的更简便的解法呢?
由于每一行的数字都是按循序排列的,所以我们很容易就想到用二分法来解决,也就是遍历每一行,然后在每一行里面进行二分法查询。
class Solution { public boolean findNumberIn2DArray(int[][] matrix, int target) { for (int i = 0; i < matrix.length; i++) { int left = 0; int right = matrix[0].length-1; while (left<=right) { int middle = (left + right) / 2; if (target == matrix[i][middle]) { return true; } if (target > matrix[i][middle]) { left = middle + 1; } else { right = middle - 1; } } } return false; } }
方法消耗情况
执行用时:0-1 ms 内存消耗:44.4 MB
时间复杂度
二分法的复杂度大家应该都知道吧,O(logn)。具体算法就是 N *(1/2)^x=1,得出来x=logn,底数为2。
所以在外面套一个循环,总的时间复杂度就为O(mlogn),底数为2
空间复杂度
由于也没有用到额外的跟n有关的空间,所以空间复杂度是O(1)。
解法三
但是,刚才的解法还是没有完全用到题目的特性,这个二维数组不仅是每行进行了排序,每列也进行了排序。
所以,该怎么解呢?
我们可以把这个数组转个角度看看,转45度角:
[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]
15 11 19 7 12 22 4 8 16 24 1 5 9 17 30 ...
下面就不写了,是不是像一个二叉树的结构了?而且每个节点的左分支是一定小于这个元素的,右分支是一定大于这个元素的。
那么根据这个特点,我们又可以写出一种更简便的算法了,也就是从第一行的最后一个数字开始,依次和目标值比较,如果目标值大于这个节点数,就把节点往下移动,也就是行数+1。如果目标值小于这个节点数,就把节点向左移动,也就是列数-1。
class Solution { public boolean findNumberIn2DArray(int[][] matrix, int target) { int i = matrix.length - 1, j = 0; while(i >= 0 && j < matrix[0].length) { if(matrix[i][j] > target) i--; else if(matrix[i][j] < target) j++; else return true; } return false; } }
方法消耗情况
执行用时:0-1 ms 内存消耗:44.5 MB
时间复杂度
代码量确实少了很多,那么时间复杂度有没有减少呢?
可以看到,只有一个while循环,从右上角开始找,如果最坏情况就是找到左下角,也就是移动到最下面一行的第一列,那么时间复杂度就是O(m+n)了。
一个是mlogn(底数为2),一个是m+n,也不能断定哪个小,但是m和n比较大的时候肯定是加法得出的结果比较小的,所以这种解法应该是最优解法了。
关于LeetCode中如何查找二维数组查找问题的解答就分享到这里了,希望以上内容可以对大家有一定的帮助,如果你还有很多疑惑没有解开,可以关注创新互联行业资讯频道了解更多相关知识。
网站名称:LeetCode中如何查找二维数组查找
文章地址:http://myzitong.com/article/pjjepd.html