题目描述

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。

你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

示例 1：

1
2
输入：nums = [1,3,4,2,2]
输出：2

算法思路

这个题目如果不要求不能修改数组并且不额外使用空间，那么这道题解法太多了，排序或者哈希表都能解决。这个题目去年我做过，但是已经忘了，只记得是二分查找，于是就看了官方题解。总结一下，大概思路是这样的：

  1. 如果一个数字重复了，我们假设它是target，我们记cnt[i]为小于等于i的数字的数量，那么对于：

  2. 1~target-1，每个数字不重复，cnt[i] <= i

  3. >=target，至少重复一个target，cnt[i] > i

  4. 则我们需要找到这个target，即刚好满足i < target,cnt[i]<=i; i >= target, cnt[i] > 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 值均加一，其他不变，亦满足条件。

对于上述情况二，我们可以用nums={1,2,4,4,4,5}看一下，4这个数字重复3次，占用了3, 6两个数字的位置，但是很容易得到，cnt[1]=1,cnt[2]=2,cnt[3]=2,cnt[4]=5,cnt[5]=6对于i<target，仍然满足cnt[i]<=i，同样对于i>=target，仍然满足cnt[i]>i。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int ans = -1;
        int l = 0, r = nums.size() - 1;
        while (l <= r) {
            int mid = (l + r) >> 1;
            int cnt = 0;
            for (auto num : nums) {
                cnt += num <= mid;
            }
            if (cnt <= mid) {
                l = mid + 1;
            }
            else {
                // cnt > mid, 这个mid有可能就是结果
                r = mid - 1;
                ans = mid;
            }
        }
        return ans;
    }
};