题目描述

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

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

样例

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

返回 2 或 3。

算法

(二分 + 抽屉原理)

1. 一共有n个坑，但是有n + 1个数，那么一定会有一个坑有2个数
2. 二分的模板选哪个都可以AC，对应的边界条件处理好就可以
3. 二分的时候，二分的不是数组下标，而是数组中的元素值，所以最后return r的时候直接就是元素值。因为这里是 将数的取值范围划分为两半 ，也就是数值大于mid的放右边，数值小于mid的去左边。
4. cnt用来统计分别落入两个范围的数字的个数，因为 左右两个区间，一定会有一个区间的数字个数大于区间长度， 那么这个多出来的，我们不断二分它，直至最后找到答案。

时间复杂度

$O(nlogn)$
每次二分的时间复杂度是$O(logn)$，把n个元素二分成n个长度为1的小区间。
因为每次二分的过程，都会遍历求解元素的个数，一共有n个元素，所以就是$O(nlogn)$

C++ 代码

class Solution {
public:
    int duplicateInArray(vector<int>& A) {
        int l = 1, r = A.size();
        while(l < r)
        {
            int mid = l + r + 1 >> 1;
            int cnt = 0;
            for(auto x : A) cnt += (x >= mid && x <= r);
            if(cnt > r - mid + 1) l = mid;
            else r = mid - 1;
        }
        return r;
    }
};

使用unordered_set的代码

class Solution {
public:
    int duplicateInArray(vector<int>& A) {
        int n = A.size();
        unordered_set<int> se;
        int res = 0;
        for(int i = 0; i < n; i ++)
        {
            if(se.count(A[i])) res = A[i];
            else se.insert(A[i]);
        }
        return res;
    }
};