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 <分界线元素的数量，若多于一半，重复的元素在<分界线这边

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

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

Solution2：快慢指针找loop，再找loop起点

和142题思路相同: //www.greatytc.com/p/e193b5216cfe
思路： 将数组的每个元素看成是链表结点，index -> value, value再作为index -> value的过程就是遍历各结点的过程。如果其中没有duplicates，n+1个位置，则访问过程是不会重复的(index和value相同的自己环除外)，即没有环。若有duplicate，则有环。而环的起点就是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;
    }
}