Find The Duplicate Number

发表于 | 分类于

Find The Duplicate Number(找到数组中的重复数字)

题目描述：

给定一个数组，其长度为n + 1，数组中的数的范围为1到n。其中有且只有一个数重复了，但是可能重复了很多次。要求在O(1)的空间，小于O(n^2)的复杂度，不改变数组的前提下找到该数。具体描述见LeetCode289

解题思路：

要求的空间过小，所以哈希表方法排除；要求复杂度小，所以暴力解法排除；不改变数组，所以交换数组的数排除；所以本题使用的是二分查找法。原理是我们假设有6个抽屉，如果一共有7个苹果，则在其中的一个抽屉中肯定有2个或者2个以上的苹果。同理，我们假设low = 1, high = n(因为数组的范围是这样)。计算得到mid = (low + high) / 2；然后遍历数组中小于或者等于mid的数。如果该数大于mid，则说明在[low, mid]中一定存在重复的数，此时将high = mid；反之，如果该数小于mid,说明在[low, mid]中肯定不存在重复的数；将low = mid + 1(注意不是low = mid,因为这种情况下，我们已经排除了这个数是mid的可能)。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int low = 1;
        int high = nums.size() - 1;
        int mid = 0;
        int count = 0;
        while(low < high){
            mid = low + (high - low) / 2; // mid作为标杆
            count = 0;
            for (int i = 0; i < nums.size(); i++){
                if (nums[i] <= mid) count++; 
                // 计算数组中小于等于mid的数
            }
            if (count > mid) high = mid;
            if (count <= mid) low = mid + 1;
            // 不同情况下改变low和high
        }
        return low;
    }
};