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: You must not modify the array (assume the array is read only). You must use only constant, O(1) extra space. Your runtime complexity should be less than O(n2). There is only one duplicate number in the array, but it could be repeated more than once.

注意题目给出的条件，只有一个重复的元素，重复的元素的数目可能超过2次(不一定只有两次)

思路一:可知这个数的范围在(1, n)之间；
首先求出mid = n/2，求出所有小于等于他的数的个数count，如果没有重复的元素，那么count <= mid时，这个要求的数一定在mid的后面

可以这样来看
1  2  3   4  5........n  (n个数)

对于任意的i（1<= i <= n），一定有小于等于i的数的个数为i，这个时候，加了一个元素，导致重复，那么小于等于这个重复的数的数字的个数一定大于这个数

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int lb = 1;
        int ub = nums.size() - 1;

        while(lb < ub){
            int count = 0;
            int mid = (lb + ub)>>1;

            for(auto &n:nums){
                if(n <= mid)
                    count++;
            }

            if(count <= mid){
                lb = mid + 1;
            }else 
                ub = mid;

        }

        return lb;
    }
};

可以采用类似链表环路的形式

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int fast = nums[nums[0]];
        int slow = nums[0];

        while(fast != slow){
            fast = nums[nums[fast]];
            slow = nums[slow];
        }

        slow = 0;
        while(fast != slow){
            fast = nums[fast];
            slow = nums[slow];
        }

        return slow;
    }
};