题目描述

给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。

示例一：

1 2	输入: [1,3,4,2,2] 输出: 2

示例二：

1 2	输入: [3,1,3,4,2] 输出: 3

题解

二分查找

之所以不使用暴力遍历查找和哈希表记录, 是因为时间复杂度或者空间复杂度超出要求.

使用cnt[i]表示nums[]数组中小于等于i 的数有多少个, 假设我们重复的数是target, 那么[1, target-1]里的所有数满足cnt[i]<=i, [target, n]里的所有数满足cnt[i]>i, 具有单调性.

以示例1为例, 列出每个数字的cnt值:

nums	1	2	3	4
cnt	1	3	4	5

示例中重复的整数是2, 我们可以看到[1, 1]中的数满足cnt[i]<=i, [2, 4]中的数满足cnt[i]>i

一旦知道了cnt[i]数组的单调性和以上的大小关系, 就可以使用二分查找来找到重复的数. 对于所有测试用例, 考虑一下两种情况:

如果测试用例的数组中 target 出现了两次，其余的数各出现了一次，这个时候肯定满足上文提及的性质，因为小于target 的数 i满足cnt[i]=i，大于等于target 的数 j满足 cnt[j]=j+1
如果测试用例的数组中target出现了三次及以上，那么必然有一些数不在 nums[]数组中了，这个时候相当于我们用 target 去替换了这些数，我们考虑替换的时候对 cnt[]数组的影响。如果替换的数i小于 target，那么 [i,target-1] 的 cnt 值均减一，其他不变，满足条件。如果替换的数 j大于等于 target，那么[target, j-1]的 cnt 值均加一，其他不变，亦满足条件。

总结来说就是, 对于每个区间[left, right], 根据mid计算出cnt的值, 然后比较mid和cnt的大小, 以比较的结果调整左右边界

public int findDuplicate(int[] nums) {
        int n = nums.length;
        int l = 1, r = n - 1, ans = -1;
        while (l <= r) {
            int mid = (l + r) / 2;
            int cnt = 0;
            for (int i = 0; i < n; i++) {
                if (nums[i] <= mid) {
                    cnt++;
                }
            }

            if (cnt <= mid) {
                l = mid + 1;
            } else {
                r = mid - 1;
                ans = mid;
            }
        }
        return ans;
    }