leetcode_find_the_duplicate_number

发表于

难度：Hard

数组在1~n之间，找出mid=(1+n)/2,统计mid出现的次数cnt，小于mid的元素出现的次数below_cnt。如果cnt=2，则得解。如果below_cnt>mid-1，则重复元素在小于mid的区间出现；否则在大于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
26
27
28
29
30
31
32
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int n = nums.size()-1;
        int low = 1;
        int high = n;
        while(low <= high)
        {
            int mid = low+(high-low)/2;
            int cnt = 0;
            int below_cnt = 0;
            for(auto &i:nums)
            {
                if(i==mid)
                    cnt++;
                else if(i<mid)
                    below_cnt++;
            }
            if(cnt >= 2)
                return mid;
            else
            {
                if(below_cnt > mid-1)
                    high = mid-1;
                else
                    low = mid+1;
            }

        }
        return 0;
    }
};

19ms，29.5%