14. 不修改數組找出重複的數字

二分出重複出現的數。

一共有 n+1 個數，每個數的取值範圍是1到n，是以至少會有一個數出現兩次。

然後我們采用分治的思想，将每個數的取值的區間[1, n]劃分成[1, n/2]和[n/2+1, n]兩個子區間，然後分别統計兩個區間中數的個數。

注意這裡的區間是指 數的取值範圍，而不是 數組下标。

劃分之後，左右兩個區間裡一定至少存在一個區間，區間中數的個數大于區間長度。

是以我們可以把問題劃歸到左右兩個子區間中的一個，而且由于區間中數的個數大于區間長度，根據抽屜原理，在這個子區間中一定存在某個數出現了兩次。

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

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