不修改数组找出重复地数字

ryluo 2020-06-19 20:57:54

给定一个长度为 n+1 的数组nums,数组中所有的数均在 1∼n 的范围内,其中n≥1。

请找出数组中任意一个重复的数,但不能修改输入的数组。

样例

给定 nums = [2, 3, 5, 4, 3, 2, 6, 7]。

返回 2 或 3。

思考题:如果只能使用 O(1)O(1) 的额外空间,该怎么做呢?

分析:

数组取值为1-n,数组地长度为n+1,那么数组中至少存在两个重复地数字。(抽屉原理)

那么,如果按照数值将数组中地值分成两部分,一部分大于n/2,另一部分小于等于n/2, 那么划分之后一定有一个区间满足,数字的个数大于区间长度,即仍然满足抽屉定理。通过这个性质就可以不断地二分下去,直到区间长度为1地时候就是需要输出的值。

为什么二分之后一定还满足抽屉定理呢?

假设不满足。也就是二分之后两个区间中数的个数都小于等于区间长度,那么总的数的个数就小于等于n,与题中数的个数为n+1矛盾。

题解:

class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        int l = 1, r = nums.size() - 1; // 值域为[1, n-1]
        while(l < r){
            int mid = l + r >> 1;

            int sum = 0;
            for (auto x: nums)
                if (x <= mid && x >= l)
                    sum ++;


            if (sum > mid - l + 1) r = mid;
            else l = mid + 1;
        }

        return l;
    }
};