面试题03. 数组中重复的数字(简单)

找出数组中重复的数字。

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

示例 1：

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

限制：2 <= n <= 100000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof

思路：

直接用set进行接收就行，如果存在就输出，不存在就add。如果是排序的话，时间复杂度为O（nlogn），HashSet的话复杂度为O（n）

思路2：

从题目描述中我们可以看出，因为所有数字都在 0 ～ n-1 的范围内，其实完全可以省掉额外的空间开辟，将每个位置的数交换映射到其对应的数组下标下面，当出现新的元素与其对应的下标中的数字相等时，即为重复数字
时间复杂度：O(n)，空间复杂度：O(1)

作者：guanpengchn
链接：https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/solution/hua-jie-suan-fa-mian-shi-ti-3-shu-zu-zhong-zhong-f/

下面的是剑指offer中对步骤的解释

以数组{2，3，1，0，2，5，3}为例，数组第0个数字是2，与它的下标不符，于是将它和下标为2的数字1交换，交换后的数组为{1，3，2，0，2，5，3}，此时第0个数组是1，仍然与它的下标不相等，继续把它和下表为1的数字3进行交换，得到数组{3，1，2，0，2，5，3}，仍不满足，继续交换第0位的数字3和第3位数字0，得到数组为{0，1，2，3，2，5，3}，这时候满足第0个数字数值为0，接着扫描下一个数字，下标1，2，3的数都满足，不用执行任何操作，接下来扫描到下标为4的数字2，由于数值和下标不相等，再比较它和下标为2的数字，此时命中，即哈希冲突了

回看记录200604

哈希思路：

如果一个数不在下标位置上，就交换这个数和他代表的下标位置上的数，当遇到另一个数时，有冲突，表示重复了，这里就找到了，理解回看记录上面的思路2，不难理解

代码1：

1
2
3
4
5
6
7
8
9
10
11
12
13
//set解决方案不用看
class Solution {
    public int findRepeatNumber(int[] nums) {
        HashSet<Integer> set = new HashSet<Integer>();
        for(int num:nums){
            if(set.contains(num))
                return num;
            else
                set.add(num);   
        } 
        return -1;
    }
}

代码2：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int findRepeatNumber(int[] nums) {
        int len = nums.length;
        //目的就是将该数值放到对应的下标的位置上，再次出现时，hash有冲突，即重复
        for (int i = 0; i < len; i++) {
            while (nums[i] != i) {//当i和数组值不一致时，交换，将i映射到nums[i]
                if (nums[i] == nums[nums[i]]) {//出现新的元素与其对应的下标中的数字相等时，即有重复
                    return nums[i];
                }
                int temp = nums[i];
                nums[i] = nums[temp];
                nums[temp] = temp;
            }
        }
        return -1;
    }
}