温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

LeetCode中怎么输出数组中重复的数字

发布时间:2021-08-12 15:56:10 来源:亿速云 阅读:157 作者:Leah 栏目:web开发

LeetCode中怎么输出数组中重复的数字,针对这个问题,这篇文章详细介绍了相对应的分析和解答,希望可以帮助更多想解决这个问题的小伙伴找到更简单易行的方法。

题目:数组中重复的数字

在一个长度为 n 的数组 nums  里的所有数字都在0~n-1的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例 1:

输入:[2, 3, 1, 0, 2, 5, 3] 输出:2 或 3

限制:2 <= n <= 100000

解法一

题目分析下来,主要的目的就是找到数组中的重复数字。

所以我们可以利用那些没有重复、成员唯一的集合,比如HashSet。

HashSet的特点就是唯一和无序,所以只要我们把数组中的数字加到HashSet中,如果出现重复数字,就会加入失败。利用这一点就可以完成解法。

class Solution {     public int findRepeatNumber(int[] nums) {         Set<Integer> set = new HashSet<Integer>();         int repeat = -1;         for (int num : nums) {             if (!set.add(num)) {                 repeat = num;                 break;             }         }         return repeat;     } }

代码还是比较简单的吧,设置一个空的HashSet集合,然后依次add数字进去,出现失败的情况(也就是add方法返回false),也就代表数字出现了重复。

方法消耗情况

执行用时:6ms 内存消耗:48.3MB

时间复杂度

由于用到了一个for单循环,复杂度为O(n),其他的代码复杂度都为O(1),包括set.add的复杂度也是O(1)。

所以总的时间复杂度为O(n)。

空间复杂度

如果set集合add一次就会占用一次空间,所以n次循环,最坏情况空间复杂度就为O(n)

解法二

这道题其实还有个题干不容易被发现,就是第一句:

长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内

这句话的意思就是,如果没有重复数字的情况下,这个数组在排序后应该是数组中下标为i的位置所在的值应该是等于i的。

也就是nums[i]=i。

打个比方,数组长度为5,那么里面的数字应该在0&mdash;&mdash;4。如果不存在重复数字的话,那么经过排序后数组应该为:

[0,1,2,3,4]

也就是nums[i]=i,

根据这一个特性,我们就可以依次把数字放到数字对应的位置上,正常来说一个数字会对应一个数字的坑位,也就是一个萝卜一个坑。

当发现一个坑有两个萝卜的时候,就是有重复数字的发生了。上代码:

class Solution {     public int findRepeatNumber(int[] nums) {         int temp;         for(int i=0;i<nums.length;i++){             while (nums[i]!=i){                 if(nums[i]==nums[nums[i]]){                     return nums[i];                 }                 temp=nums[i];                 nums[i]=nums[temp];                 nums[temp]=temp;             }         }         return -1;     } }

简单说下:

遍历数组,当发现数组下标数字不等于该下标对应位置上的数字的时候,也就是nums[i]!=i,那么我们就把nums[i]数字  放到nums[i]位置上,一直到nums[i]==i。按照一个坑位一个萝卜,所以当你的坑位被同样的萝卜(数字)占到的时候,这个萝卜就是重复的那个数字了。

假如数组为[3,1,4,2,2]

  • i=0的时候,nums[i]=3。3 !=1。所以把3放到num[3]的位置,数组变成了[2,1,4,3,2]。

  • 2!=0,while条件true,继续置换,数组变成了[4,1,2,3,2]。

  • 4!=0,while条件true,继续置换,数组变成了[2,1,2,3,4]。

  • 2!=0,while条件true,但是此时位置为2的坑位已经被同样的数字占据了,所以这个2就是重复数字,return。

方法消耗情况

执行用时:0&mdash;1ms 内存消耗:46.4MB

时间复杂度

有一个for循环,复杂度为O(n),但是在循环中,while置换最多有可能发生n次,其实也就是一个排序的过程。但是这个while排序只会发生一次,如果发生了最大n次,那么也就代表后续不用排序了。所以复杂度就是O(n+n),也就是O(n).

空间复杂度

在空间方面,由于用的还是原数组,只是多了一个变量temp,所以空间复杂度为O(1)

关于LeetCode中怎么输出数组中重复的数字问题的解答就分享到这里了,希望以上内容可以对大家有一定的帮助,如果你还有很多疑惑没有解开,可以关注亿速云行业资讯频道了解更多相关知识。

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI