题目描述

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中第一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。
返回描述：
如果数组中有重复的数字，函数返回true，否则返回false。
如果数组中有重复的数字，把重复的数字放到参数duplication[0]中。（ps:duplication已经初始化，可以直接赋值使用。）

代码

方法一

如果没有重复数字，那么正常排序后，数字i应该在下标为i的位置，所以思路是重头扫描数组，遇到下标为i的数字如果不是i的话，
（假设为m),那么我们就拿与下标m的数字交换。在交换过程中，如果有重复的数字发生，那么终止返回ture

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

方法二

class Solution {
public:
    // 2, 3, 1, 0, 2, 5
    // 1, 3, 2, 0, 2, 5
    // 3, 1, 2, 0, 2, 5
    // 0, 1, 2, 3, 2, 5
    int duplicate(vector<int> &numbers) {
        unordered_map<int, int> hash;
        for (int i = 0; i < numbers.size(); i++) {
            hash[numbers[i]]++;
            if (hash[numbers[i]] > 1) {
                return numbers[i];
            }
        }
        return -1;
    }
};