文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

LeetCode题解-二维数组查找

2024-12-03 12:55

关注

二维数组中的查找

在一个 n * m 的二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个高效的函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。

示例:

现有矩阵 matrix 如下:

  1.  
  2. [1, 4, 7, 11, 15], 
  3.  
  4. [2, 5, 8, 12, 19], 
  5.  
  6. [3, 6, 9, 16, 22], 
  7.  
  8. [10, 13, 14, 17, 24], 
  9.  
  10. [18, 21, 23, 26, 30] 
  11.  

给定 target = 5,返回 true。

给定 target = 20,返回 false。

限制:

  1. 0 <= n <= 1000 0 <= m <= 1000 

解法一

题目理解起来很简单,一个二维数组,一个数字。判断数组里面有没有这个数字。

另外还有一个提干是每一行每一列都是数字递增,待会再看看这个题干怎么利用起来。

如果只是一个数组里面找数字,那么很容易想到的就是直接遍历。

  1. class Solution { 
  2.     public boolean findNumberIn2DArray(int[][] matrix, int target) { 
  3.         if (matrix == null || matrix.length == 0 || matrix[0].length == 0) { 
  4.             return false
  5.         } 
  6.         int rows = matrix.length, columns = matrix[0].length; 
  7.         for (int i = 0; i < rows; i++) { 
  8.             for (int j = 0; j < columns; j++) { 
  9.                 if (matrix[i][j] == target) { 
  10.                     return true
  11.                 } 
  12.             } 
  13.         } 
  14.         return false
  15.     } 

方法消耗情况

  1. 执行用时:0-1 ms 
  2. 内存消耗:44.3 MB 

时间复杂度

由于用到了二维数组的遍历,所以时间复杂度就是O(mn),用到了时间复杂度的乘法计算。

空间复杂度

除了本身的数组,只用到了几个变量,所以空间复杂度是O(1)。

解法二

接下来我们就看看怎么利用刚才说到的数字递增题干,得出新的更简便的解法呢?

由于每一行的数字都是按循序排列的,所以我们很容易就想到用二分法来解决,也就是遍历每一行,然后在每一行里面进行二分法查询。

  1. class Solution { 
  2.      public boolean findNumberIn2DArray(int[][] matrix, int target) { 
  3.         for (int i = 0; i < matrix.length; i++) { 
  4.             int left = 0; 
  5.             int right = matrix[0].length-1; 
  6.             while (left<=right) { 
  7.                 int middle = (left + right) / 2; 
  8.                 if (target == matrix[i][middle]) { 
  9.                     return true
  10.                 } 
  11.                 if (target > matrix[i][middle]) { 
  12.                     left = middle + 1; 
  13.                 } else { 
  14.                     right = middle - 1; 
  15.                 } 
  16.             } 
  17.         } 
  18.         return false
  19.     } 

方法消耗情况

  1. 执行用时:0-1 ms 
  2. 内存消耗: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]

  1.         15 
  2.       11  19 
  3.     7   12   22  
  4.   4    8   16    24 
  5. 1   5    9    17    30 
  6.  
  7. ... 

下面就不写了,是不是像一个二叉树的结构了?而且每个节点的左分支是一定小于这个元素的,右分支是一定大于这个元素的。

那么根据这个特点,我们又可以写出一种更简便的算法了,也就是从第一行的最后一个数字开始,依次和目标值比较,如果目标值大于这个节点数,就把节点往下移动,也就是行数+1。如果目标值小于这个节点数,就把节点向左移动,也就是列数-1。

  1. class Solution { 
  2.     public boolean findNumberIn2DArray(int[][] matrix, int target) { 
  3.         int i = matrix.length - 1, j = 0; 
  4.         while(i >= 0 && j < matrix[0].length) 
  5.         { 
  6.             if(matrix[i][j] > target) i--; 
  7.             else if(matrix[i][j] < target) j++; 
  8.             else return true
  9.         } 
  10.         return false
  11.     } 

方法消耗情况

  1. 执行用时:0-1 ms 
  2. 内存消耗:44.5 MB 

时间复杂度

代码量确实少了很多,那么时间复杂度有没有减少呢?

可以看到,只有一个while循环,从右上角开始找,如果最坏情况就是找到左下角,也就是移动到最下面一行的第一列,那么时间复杂度就是O(m+n)了。

一个是mlogn(底数为2),一个是m+n,也不能断定哪个小,但是m和n比较大的时候肯定是加法得出的结果比较小的,所以这种解法应该是最优解法了。

空间复杂度

同样,空间角度,没有使用额外的和n相关的空间,所以空间复杂度为O(1)

参考

https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof

本文转载自微信公众号「码上积木」,可以通过以下二维码关注。转载本文请联系码上积木公众号。

 

来源: 码上积木内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯