Find the Duplicate Number

发表于 | 分类于

Find the Duplicate Number

题目描述：

给定一个包含n+1个数的数组，数组中的数的范围是1到n；其中有且只有存在一个数重复，且可能重复多次。要求找到这个重复的数。

例子：

具体描述见LeetCode289

解题思路：

我们这边利用二分查找的方式来解题。既然存在一个重复的数，那对于中位数而言，重复的数肯定在数量较多的那一侧。所以我们每次只要遍历所有的数找到比中位数小的数的数量。根据统计的数量进行对low和high的调整即可。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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;
            count = 0;
            for (int i = 0; i < nums.size(); i++){
                if (nums[i] <= mid) count++;
            }
            if (count > mid) high = mid;
            if (count <= mid) low = mid + 1;
        }
        return low;
    }
};