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

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—1ms 内存消耗：46.4MB

时间复杂度

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

空间复杂度

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

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