问题抽象

n+1个数，值域[1,n]，找出重复数

算法：抽屉原理，分治

难点在于，不能标记数组，但是有一个重要条件：数的值域比区间长度小，这保证了必定有重复数，但是怎么利用这个条件呢？

关键在于想到，n+1个数放到1~n个坑中必定有重复，但是重复数在哪个坑呢？这也是题目所求。我们可以考虑去缩小坑的范围：把这n+1个数按值的范围放在n/2个坑中，这n/2个坑可以是1~n/2坑，或者n/2+1~n坑。其中至少有一个会有重复，我们在重复的范围坑中继续去分n/4个坑，依次类推，直到坑的大小为1，则该坑必定为重复坑。

这道题是分治的思想，‘分’指的是把坑一分为二，‘治’指的是比较左右两坑容纳数的多少。此题没有用递归的写法，是因为递归适合平等对待‘分’的各部分，而这道题是‘舍一取一’，因此用迭代的做法（类似二分）更合适。

时间复杂度

$O(NlogN)$

代码

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