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.

Input: [1,3,4,2,2]
Output: 2

1. 利用数组跳转到办法（类似于LL中找环） 为了使用Cycle Detection,首先需要把数组转换成LL（这也是因为题目里规定了nums中只包含了1~n的数字）， 所以可以从0开始，下一个的index为上一个index指向的值(即nums[index])，这样把array转化成了LL。 其中两个指针slow每次只移动一格，fast指针移动两跳。相遇后再去找相遇点

int len = nums.length;

int slow = nums[0];
int fast = nums[nums[0]];
while (slow != fast) {
    slow = nums[slow];
    fast = nums[nums[fast]];
}

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

return start;

1. 虽然数组本身不是有序的，但是数据集1~n是有序的，我们可以对1~n进行二分查找，每次找到的数为mid，可以判断nums中比mid大或者小的数出现的次数，多余一半的话，这说明重复的那个数在(1,mid) or (mid, n)的某一次，进而不断的二分查找缩小范围

   class Solution {
    public int findDuplicate(int[] nums) {
        int len = nums.length;
        int n = len - 1;
        int start = 1;
        int end = n;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            int count = count(nums, mid);
            if (count > mid) {
                start = mid;
            } else {
                end = mid;
            }
        }
   
        if (count(nums, start) >= start)
            return start;
        else
            return end;
    }
   
    // get the count of the nums in nums which is not larger than val
    private int count(int[] nums, int val) {
        int count = 0;
        for (int i : nums) {
            if (i >= val)
                count++;
        }
        return count;
    }
   }