287.Find the Duplicate Number

287.Find the Duplicate Number

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Note:

1. You must not modify the array (assume the array is read only).
2. You must use only constant, O(1) extra space.
3. Your runtime complexity should be less than O(n2).
4. There is only one duplicate number in the array, but it could be repeated more than once.

之前也有过与duplicate相关的Array类题目，大多是删除元素，而这次要求找出其中的duplicates，本来不是什么很难的要求，但由于有了题目上的种种限制，比如不能改变Array(也就不能通过排序的方法判断相邻元素是否相等)，时间复杂度低于O(n2)，这道题目就有了难度。

对于这样的数组，我们很难将其与二分查找联系起来，不过它们之间确实有着练习

既然是从1~n的n+1个数，那么根据抽屉原理就必然有一个重复的数，那么先计算mid，算出mid之后计算数组中比mid小的数有几个，如果多于mid个，根据抽屉原理，则说明区间[low,mid-1]必存在重复，否则调整区间到[mid+1,high]。代码如下:

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int low=0,size=nums.size(),high=size-1,mid=0,count=0,i=0;
        while(low<=high){
            count=0;
            mid=low+(high-low)/2;
            for(i=0;i<size;i++){
                if(nums[i]<=mid)
                    count++;
            }
            if(count>mid)
                high=mid-1;
            else
                low=mid+1;
        }
        return low;
    }
};