题目

1
2
3
4
5
6
7
8
统计一个数字在排序数组中出现的次数。

例如输入排序数组 [1,2,3,3,3,3,4,5] 和数字 3，由于 3 在这个数组中出现了 4 次，因此输出 4。

样例
输入：[1, 2, 3, 3, 3, 3, 4, 5] ,  3

输出：4

题解

法一：遍历或用vector自带count函数

点击查看
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int getNumberOfK(vector<int>& nums , int k) {
        int cnt = 0;
        for(auto c : nums){
            if(c == k) cnt++;
        }
        return cnt;
    }
};
//-------------------------------------------------
class Solution {
public:
    int getNumberOfK(vector<int>& nums , int k) {
        
        return count(nums.begin(), nums.end(), k);
    }
};

法二：手写二分

点击查看
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int getNumberOfK(vector<int>& nums , int k) {
        int l = 0, r = nums.size() - 1;
        if(nums.empty()) return 0;
        while(l < r){
            int x = l + r >> 1;
            if(nums[x] >= k) r = x;
            else l = x + 1;
        }
        if(nums[l] != k) return 0;
        int a = l;
        l = 0, r = nums.size() - 1;
        while(l < r){
            int x = l + r + 1 >> 1;
            if(nums[x] <= k) l = x;
            else r = x - 1;
        }
        int b = l;
        
        return b - a + 1;
    }
};

法三：multiset

点击查看
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int getNumberOfK(vector<int>& nums , int k) {
       
        multiset<int> s;
        
        for(auto c : nums) s.insert(c);
        
        return s.count(k);
        
    }
};

法四：lower_bound(upper_bound)

点击查看
1
2
3
4
5
6
7
8
9
class Solution {
public:
    int getNumberOfK(vector<int>& nums , int k) {
        vector<int>::iterator pos1 = lower_bound(nums.begin(), nums.end(), k);
        vector<int>::iterator pos2 = upper_bound(nums.begin(), nums.end(), k);
        
        return pos2 - pos1;
    }
};