LeetCode 287. Find the Duplicate Number

题目描述

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

示例 1:

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

示例 2:

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

说明：

不能更改原数组（假设数组是只读的）。
只能使用额外的 $O(1)$ 的空间。
时间复杂度小于 $O(n^2)$ 。
数组中只有一个重复的数字，但它可能不止重复出现一次。

解题思路

抽屉原理：桌上有十个苹果，要把这十个苹果放到九个抽屉里，无论怎样放，我们会发现至少会有一个抽屉里面放不少于两个苹果。

方法：二分查找
思路：这道题要求我们查找的数是一个整数，并且给出了这个整数的范围（在 $1$ 和 $n$ 之间，包括 $1$ 和 $n$），并且给出了一些限制，于是可以使用二分查找法定位在一个区间里的整数。

这个问题应用二分法与绝大多数其它问题应用二分法的不同点是：正着思考是容易的，即思考哪边区间存在重复数是容易的，因为依然是有抽屉原理做保证。我们依然通过一个具体的例子来分析应该如何编写代码。

以 [1, 2, 2, 3, 4, 5, 6, 7] 为例，一共 8 个数，n + 1 = 8，n = 7，根据题目意思，每个数都在 1 和 7 之间。

例如：区间 [1, 7] 的中位数是 4，遍历整个数组，统计小于等于 4 的整数的个数，至多应该为 4 个。换句话说，整个数组里小于等于 4 的整数的个数如果严格大于 4 个，就说明重复的数存在于区间 [1, 4]，它的反面是：重复的数存在于区间 [5, 7]。

于是，二分法的思路是先猜一个数（有效范围 [left, right]里的中间数 mid），然后统计原始数组中小于或等于这个中间数的元素的个数 cnt，如果 cnt 严格大于 mid，（注意我加了着重号的部分“小于或等于”、“严格大于”）依然根据抽屉原理，重复元素就应该在区间 [left, mid] 里。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

int findDuplicate(int* nums, int numsSize){
    int low = 0, high = numsSize - 1, mid;

    while(low <= high){
        mid = (low + high) / 2;
        int cnt = 0;

        for(int i = 0; i < numsSize; i++){
            if(nums[i] <= mid)
                cnt++;
        }

        // 根据抽屉原理，严格小于 4 的数的个数如果大于等于 4 个，
        // 此时重复元素一定出现在 [1, 3] 区间里
        if(cnt > mid)
            // 重复的元素一定出现在 [left, mid - 1] 区间里
            high = mid - 1;
        else
            // if 分析正确了以后，else 搜索的区间就是 if 的反面
            // [mid, right]
            // 注意：此时需要调整中位数的取法为上取整
            low = mid + 1;
    }
    return low;
}

复杂度分析：

时间复杂度：$O(NlogN)$，二分法的时间复杂度为 $O(logN)$，在二分法的内部，执行了一次 for 循环，时间复杂度为 $O(N)$，故时间复杂度为 $O(NlogN)$。
空间复杂度：$O(1)$，使用了一个 cnt 变量，因此空间复杂度为 $O(1)$。