思路

• n+1个苹果装在n个抽屉里
• 有一个抽屉至少装了两个苹果
• 二分找到mid
• 然后每次统计l<=num<=mid的数的长度
• 如果这个长度比mid - l + 1小，那么重复的数就在左边否则在右边

class Solution {
    public int findDuplicate(int[] nums) {
        int len = nums.length;
        int n = len - 1;
        int l = 1;
        int r = n;
        while(l < r){
            int mid = l + r >> 1;
            int leftLen = mid - l + 1;
            int cnt = 0;
            for(int item : nums){
                if(item >= l && item <= mid)
                    cnt++;
            }
            if(cnt > leftLen)
                r = mid;
            else
                l = mid + 1;
        }
        return r;
    }
}