Find the Duplicate Number

发表于 | 分类于

Find the Duplicate Number

题目描述：

给定一个数组长度为n+1;其中只包含着1~n的数且只有一个数出现了重复，要求找到这个数。

例子：

具体描述见LeetCode287

解题思路：

我们考虑用二分查找的方式来找到这个数。我们先找到中间数mid;然后找到数组中找到小于等于mid数的个数；如果个数大于mid说明重复的数在low~mid之间。

代码如下：

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;
    }
};