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.

Solution1：Binary Search in value domain

思路： 二分值域，并count <分界線元素的數(shù)量，若多于一半，重復(fù)的元素在<分界線這邊

屏幕快照 2017-09-07 下午1.36.58.png

Time Complexity: O(NlogN) Space Complexity: O(1)

Solution2：快慢指針找loop，再找loop起點

和142題思路相同: http://m.itdecent.cn/p/e193b5216cfe
思路： 將數(shù)組的每個元素看成是鏈表結(jié)點，index -> value, value再作為index -> value的過程就是遍歷各結(jié)點的過程。如果其中沒有duplicates，n+1個位置，則訪問過程是不會重復(fù)的(index和value相同的自己環(huán)除外)，即沒有環(huán)。若有duplicate，則有環(huán)。而環(huán)的起點就是duplicate的元素，就變成了和142一樣的問題，快慢指針方法。

屏幕快照 2017-09-07 下午1.20.46.png

Time Complexity: O(N) Space Complexity: O(1)

Solution1 Code：

class Solution1 {
    public int findDuplicate(int[] nums) {
        int n = nums.length;
        int start = 1;
        int end = n;
        
        while(start < end) {
            int mid = start + (end - start) / 2;
          
            int count = 0;
            for(int i = 0; i < n; i++) {
                if(nums[i] <= mid) count++;
            }
            
            if(count <= mid) start = mid + 1;
            else end = mid;
        }
        return start;
    }
}

Solution2 Code：

class Solution {
    public int findDuplicate(int[] nums) {
        
        // start with nums[0] is also ok, but need to change "start' from nums[0] as well
        int slow = 0; 
        int fast = 0;
        
        // make both slow and fast in the loop, 
        // and stop when they meet
        
        while(true) { //since the input's index is rigid
            slow = nums[slow];
            fast = nums[nums[fast]];
            if(slow == fast) break;
        }
        
        // find the pos the cycle begins, which has the duplicate number 
        int start = 0;
        while(start != slow) {
            start = nums[start];
            slow = nums[slow];
        }
        return slow;
    }
}