287. Find the Duplicate Number

Given an arraynumscontainingn+ 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

解题方法

透過檢查數量去決定重複會在哪一區

    public int findDuplicate(int[] nums){
        //corner case
        if(nums == null || nums.length == 0){
            return -1;
        }

        int start = 1;
        int end = nums.length - 1;
        while(start + 1 < end){
            int mid = start + (end - start) / 2;
            int cnt = countNum(nums, mid);
            if(cnt > mid){
                end = mid;
            }else{
                start = mid;
            }
        }

        if(countNum(nums, start) > start){ //consider original case
            return start;
        }
        return end;
    }

    private int countNum(int[] nums, int target){
        int cnt = 0;
        for(int i = 0; i < nums.length; i++){
            if(nums[i] <= target){
                cnt++;
            }
        }
        return cnt;
    }