题目描述

找出数组中重复的数字。

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

示例 1：

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

限制：

$2 <= n <= 100000$

---

算法 1

(哈希表) $O(n)$

遍历数组，判断当前数是否在哈希表中，如果在则当前数就是一个重复的数，直接返回，否则将当前数加入到哈希表中。

时间复杂度

$O(n)$

空间复杂度

$O(n)$

C++ 代码

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        unordered_map<int, int> hash;
        for (auto x : nums) {
            if (hash.count(x)) return x;
            hash[x] ++ ;
        }
        return -1;
    }
};

算法 2

(原地交换) $O(n)$

题目已知所有数的范围在 $[0, n - 1]$ 之间，且有重复数字，我们把每个数放在它的下标位置上，那么对于重复数字必然会出现它的位置上已经放上了该数字。

根据以上原理，遍历数组，从前往后扫描每个下标 $i$ 和数 $nums[i]$，只要当前下标和数不对应（不相等），则判断下标 $nums[i]$ 和这个下标上的数 $nums[nums[i]]$ 是否对应，如果对应则当前数就是重复数字，直接返回，否则交换这两个数，循环此操作。

时间复杂度

$O(n)$

空间复杂度

$O(n)$

C++ 代码

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        for (int i = 0; i < nums.size(); i ++ ) {
            while (nums[i] != i && nums[nums[i]] != nums[i]) swap(nums[i], nums[nums[i]]);
            if (nums[i] != i && nums[nums[i]] == nums[i]) return nums[i];
        }
        return -1;
    }
};