题目描述

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

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

数据范围

1≤n≤1000

样例

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

思考题：如果只能使用 O(1) 的额外空间，该怎么做呢？

方法一：分治 O(nlogn)

因为数组中元素的值都在 1~n 之间，所以可以通过划分区间来判断，其中也涉及到了抽屉原理。

抽屉原理：一共 n 个柜子，现在要放 n+1 把钥匙，那么就一定会有 1 个柜子里放 2 把钥匙。在这道题中，1~n 区间内一定会至少有一个值，它存在多个数。

这里的区间不是数组下标而是元素的值，统计数组中元素的值再左区间内的个数，如果统计结果大于左区间最多应该存在的个数，说明该区间内有元素是重复的，则进入这个区间进行操作。

不断的将区间进行划分，重复上述操作，最终找到对应的元素。

我们拿题目的样例来举例，数组元素为 [2, 3, 5, 4, 3, 2, 6, 7] ，根据题意可知当数组元素个数为 n 时，数组中最大元素要小于等于 n-1 ，故初始化 l=1,r=n-1

第一步： 先计算 mid=(1+7)/2=4 ，因此可以根据 mid 划分成左区间 1~4 以及右区间 5~7 。

计算数组中在左区间的数的个数，其中包含 2,3,4,3,2 共 5 个数大于正常最大左区间数 4 ，说明在 1~4 这个范围存在重复的元素，故更新右端点 r=mid=4 。

第二步： 对 l 和 r 继续取 mid 得 mid=(1+4)/2=2 ，因此可以划分成左区间 1~2 和右区间 3~4 。

计算数组中在左区间的数的个数，其中包含 2,2 共 2 个数等于最大左区间数 2 ，故更新左端点 l=mid+1=3 。

第三步： 取 mid=(3+4)/2=3 ，因此可以划分成左区间 3 和右区间 4 。

计算数组中左区间的数的个数，其中包含 3,3 共 2 个数大于正常最大左区间数 1 ，故更新右端点 r=mid=3 。

第四步： 由于此时 l=r 不满足循环条件 l<r ，故退出循环，返回 r=3 即最终答案。

class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        int l = 1, r = nums.size() - 1;
        while (l < r)
        {
            //划分区间：[l,mid]和[mid+1,r]
            int mid = l + r >> 1;
            int s = 0;    //统计数值在左区间的元素个数
            for (auto i : nums)   s += i >= l && i <= mid;
            //如果统计结果大于左区间的总个数，说明该区间内存在重复元素，否则在右区间存在重复元素
            if (s > mid - l + 1)   r = mid;
            else    l = mid + 1;
        }
        return r;
    }
};

欢迎大家在评论区交流~