题目描述

给定一个长度为 n+1 的数组nums，数组中所有的数均在 1∼n 的范围内，其中 n≥1。

请找出数组中任意一个重复的数，但不能修改输入的数组。

样例

给定 nums = [2, 3, 5, 4, 3, 2, 6, 7]。

返回 2 或 3。

算法1

(哈希表) $O(n)$

记录每个数出现的次数，遍历数组对于出现超过一次的数就是重复的元素

时间复杂度

时间复杂度为 $O(n)$，额外空间复杂度为 $O(n)$

C++ 代码

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

算法2

(二分) $O(nlogn)$

按数值 [1, n] 二分，n + 1 个数 n 个位置，根据抽屉原理肯定有两个数放在了同一个位置，即重复的元素

1. l = 1, r = n, mid = l + r >> 1，数值二分区间 [l, mid] [mid + 1, r] （包含 mid 和不包含 mid 两种分法都行）
2. 每次枚举数组中在值为 x >= l && x <= mid 的个数 cnt，即值在区间 [l, mid] 中元素的个数
3. 二分的条件，只要数的个数 cnt 大于数值区间的长度那么重复的数一定就在区间 [l, mid] 内，否则就在另一半区间 [mid + 1, r] 内

时间复杂度

二分的时间复杂度为 $O(logn)$，每次内部需要迭代 n 次统计值在区间 [l, mid] 的元素个数，所以总的时间复杂度为 $O(nlogn)$

C++ 代码

class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        int l = 1, r = nums.size() - 1;
        while (l < r)
        {
            int mid = l + r >> 1; // 数值划分 [l, mid] [mid + 1, r]，不是下标
            int cnt = 0;
            for (auto x : nums)
                // 比值 l 大且比值 mid 小的数的个数
                if (x >= l && x <= mid)
                    cnt ++ ;

            // 如果区间 [l, mid] 中元素的个数大于区间长度，说明就有会重复的数
            if (cnt > mid - l + 1) r = mid;
            else l = mid + 1;
        }
        return l;
    }
};