剑指offer题目训练2：找出数组中重复的数字，不允许修改数组

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

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

样例

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

返回 2 或 3。

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

1. 思路，本题不允许修改数组元素，考虑到所有数均保证在1-n范围内，可以把1-n这个n个位置作为一个有序数组来看， 对于数组元素nums[i]总能从1-n中找到其应该放的位置。

   我们可以考虑用分治思想来解决，对于1-n这个有序数组，如果没有nums[i] 重复元素,则能保证左边数个数==右边数个数。如果有重复元素，重复元素一定在数多的一边。

   于是我们采用二分法，每次统计左右两边数的个数，往数多的地方分治，最终会找到重复的数。

   2.先分享下雪大的二分查找模板，这个比较容易混淆

3.代码如下：

class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        //已知长度一定为n+1
        int n=nums.size()-1;
        int l=1,r=n;
        while(l<r){
            int mid=l+r>>1;
            int s=0;
            for(auto x:nums){
                //统计左边数个数
                if(x>=l&&x<=mid){
                    s++;
                }
            }
            //如果左边数个数>平均数
            if(s>mid-l+1>0){
                //往左边找
                r=mid; 
            }else{
                l=mid+1;
            }
        }
        return r;  //l==r了，输出最终的结果
    }
};