Find the Duplicate Number

https://leetcode.com/problems/find-the-duplicate-number/
给定一个数组长度N+1，这个数组都是由0~N的整数组成，并且一定有一个数字出现了不止1次，求出这个数字

方法1： 抽屉原则

• 利用二分查找，（注意这个二分是针对0~N进行二分，不是怼nums里面的值进行二分）
• 每次找到整数mid，就判断nums中小于mid的数有多少个（假设有cnt个），如果(cnt<= mid)，那么重复的数字一定不再left~mid之间，具体原理可参见抽屉原理,比较巧妙

 public int findDuplicate(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            int cnt = 0;
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] <= mid) {
                    cnt++;
                }
            }

            if (cnt <= mid) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return right;
    }

方法二： 类似链表法，先记录，还没看懂
参考文献：https://www.cnblogs.com/grandyang/p/4843654.html

 public int findDuplicate2(int[] nums) {
        int slow = 0, fast = 0, t = 0;
        while (true) {
            slow = nums[slow];
            fast = nums[nums[fast]];
            if (slow == fast) {
                break;
            }
        }

        while (true) {
            slow = nums[slow];
            t = nums[t];
            if (slow == t) {
                break;
            }
        }
        return slow;
    }