LeetCode题解—重复数字

前言

本来今天应该继续说Android系统方面的知识，但是我发现内容有点多，写不完了😅。

那，为了保证文章的质量，所以今天就发一篇算法题顶上了～❤️

算法题也是面试常考的项，之前也说过，虽然用到的比较少，但是可以从算法题中考验一个程序员基本的逻辑思维。

今天和大家看看剑指 Offer上的一题：数组中重复的数字。

题目：数组中重复的数字

在一个长度为 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——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)

总结

以后也会偶尔来几次算法题练习，因为我自己本身的算法题也做的不多，所以如果有说的不对地方或者需要讨论的地方可以在讨论群发表自己的看法。感谢大家了。

参考

https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/