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 thanO(n^2).
4. There is only one duplicate number in the array, but it could be repeated more than once.

General Solution:

Same as missing number, using nums[i] store i+1, if dup change nums[i] to negative, detect negative, add the number to result list.

Solution particular for this problem:

Special Conditions for this question:

• only one number has duplicates in the array
• all the numbers are positive

Method1 Binary Search:

Find the median between 1 to n, count the number of elements <= median in the array. if no dups, number of elements <= median will equal to number of elements > median, which one contains more elements than that one contains the duplicate number.

public int findDuplicate(int[] nums) {
        if(nums == null || nums.length == 0){
            return 0;
        }

        int min = 1;
        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){
              min = mid + 1;
            }else{
              max = mid;
            }
        }
        return min;

}

Method2 Linked List Cycle detection:

ex:

arr_index: 0 1 2 3
value      1 2 3 3

see it as a linked list: 0->1->2->3->3->3->3->3, we need to find position 3 which is a loop.

Using the slow pointer, fast pointer method, slow pointer will move to nums[i], fast pointer will move to nums[nums[i]], when they meet with each other, loop detect.

    public int findDuplicate(int[] nums) {
        int slow = 0;
        int fast = 0;
        do{
            slow = nums[slow];
            fast = nums[nums[fast]];
        }while(slow!=fast);
        int start = 0;

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

    }