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.

思路

根据题意，题目给的是一个包含1到n+1的integer数组，其中不重复的数是（1-n）个，也就是说至少有2个数是重复。现在需要找出这个数来。

试想，给定一个数 m：

• 如果比 m 小的元素都没有重复的，在整个数组里面小于等于 m 元素的个数应该恰好为 m；
• 如果比 m 小的元素大于 m 个，那么很显然，重复的数字在 1 到 m 之间。

所以可以用二分法来做。

1. 停止条件是while(start <= end)
2. 先找mid（因为数是从1 - n + 1， 所以mid就可以代表任意给定一个数m)
3. 遍历数组，在数组中找nums[i] < mid的个数count。
4. 如果count > mid， 说明重复得数字一定出现在1- mid之间，更新end = mid -1;
5. 如果count <= mid, 说明重复得数字一定出现在mid - end之间，更新start = mid + 1;
6. 最后返回start即为重复的数。

public class Solution {
    /*
     * @param nums: an array containing n + 1 integers which is between 1 and n
     * @return: the duplicate one
     */
    public int findDuplicate(int[] nums) {
        // write your code here
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int start = 1;
        int end = nums.length;
        int count = 0;
        
        while (start <= end) {
            int mid = start + (end - start) / 2;
            count = 0;
            
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] <= mid) {
                    count++;
                }
            }
            if (mid < count) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        return start;
    }
}