寻找数组中重复的数字

WYMr4him / 2023-07-28 / 原文

寻找数组中重复的数字

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

1 <= n <= \(10^5\)
nums.length == n + 1
1 <= nums[i] <= n
nums 中 只有一个整数 出现 两次或多次 ，其余整数均只出现一次

二分

题目给出了所有的数字都在[1, n]的范围内, 那我可以先去开一个数组统计一下情况. 假设令cnt[i]表示数组内小于等于i的元素的个数. 假设输入样例为1, 3, 4, 2, 2. 那么cnt数组就为:

i	1	2	3	4
cnt[i]	1	3	4	5

如果一个数字x出现多次, 其他数字出现一次, 那么在x的左边(i < x), cnt[i]一定都小于i, 而当i >= x时, cnt[i]一定都大于i. cnt数组因此是单调递增的, 可以对其进行二分查找, 找到第一个cnt[i] > i 的i.

int findDuplicate(vector<int>& nums) {
    int n = nums.size();
    int l = 0, r = n - 1, res = -1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        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;
            res = mid;
        }
    }
    return res;
}