题目描述

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。To do it!
示例输入：[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3
限制：2 <= n <= 100000

题解

c++ 1s $10^7$ ~ $10^8$
暴力 $O(n^2)$ 该题 maxn = 100000，时间超限
不同数据范围对应的时间复杂度和算法选择

排序遍历

对数组排序，然后遍历，遇到重复的数字则返回。

// 排序遍历 O(nlogn)
class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        for (int i = 1; i < nums.size(); ++i) {
            if (nums[i - 1] == nums[i])
                return nums[i];
        }
        return -1;
    }
};

时间复杂度：O(nlog(n))，空间复杂度：O(1)

哈希表

遍历数组，使用哈希表记录数组的各个数字，遇到重复数字则返回。

// 哈希，一次遍历 时间 O(n) 空间 O(n)
class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        unordered_set<int> numsHash;
        for (int num : nums) {
            if (numsHash.find(num) != numsHash.end())
                return num;
            numsHash.emplace(num);
        }
        return -1;
    }
};

时间复杂度：O(n)，空间复杂度：O(n)

原地交换

题目说明长度为 n 的数组 nums 里所有数字都在 0 ~ n-1 的范围内。所以该数组的索引和元素是一对多的关系，遍历数组并通过交换操作，使索引和元素值一一对应，即 nums[i] = i。通过数组索引和元素值的对应关系，起到与哈希表等价的作用，可以理解为利用原数组的空间作为哈希存储空间。

// 数组 nums 长度为 n，所有数字都在 0～n-1 的范围内
// 原地哈希，将数组本身作为哈希表，时间 O(n) 空间 O(1)
class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; ) {
            if (nums[i] == i) { ++i; continue; }
            if (nums[i] == nums[nums[i]]) return nums[i];
            swap(nums[i], nums[nums[i]]);
        }
        return -1;
    }
};