LC 287 Find the Duplicate Number(M)

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.

public int findDuplicate(int[] nums)

边界条件 如果只有一个值 返回0；

解题思路 2分查找， 或 环形查找

2分查找，根据抽屉原理，我们可以知道duplicate number 是在mid 的左边还是右边，以此类推，我们可以逐渐缩小范围，直至最后找到该duplicate number

public int findDuplicate(int[] nums) {
    if(nums.length<2)
        return 0;
    int min = 0;
    int max = nums.length -1;
    while(min<= max){
        // 取 中值
        int mid = min + (max - min) /2;
        int count = 0;
        for(int i = 0; i < nums.length; i++){
            ／／统计有多少小于中值
            if(nums[i]<=mid){
                count ++;
            }
        }
        if(count > mid){
            max = mid-1;
        }else{
            min = mid +1;
        }
    }
    return min;
}

环形查找 如果array 中所有的数都是不同的话，那么下标和数是一一对应的关系，否则，下标和数就是多对一的关系。这样的话，如果我们每次都把下标对应的那个数作为新的下标，那么它最后会变成一个环。根据这个环我们就可以找到重复的那个数。

public int findDuplicate(int[] nums) {
    int slow = 0;
    int fast = 0;
    // 2倍快索 和一倍同时开始，直到相遇
    do {
        slow = nums[slow];
        fast = nums[nums[fast]];
    } while(slow != fast);
    int find = 0;
    while (find != slow) {
        find = nums[find];
        slow = nums[slow];
    }
    return find;
}