跟着姚桑学算法-数字在排序数组中出现的次数

题. 数字在排序数组中出现的次数

统计一个数字在排序数组中出现的次数。

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

数据范围
数组长度 [0,1000]。

样例

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

输出：4

【题解】--- STL运用

方法一：使用有序多重集合multiset；

方法二：遍历vector，计数；

方法三：使用lower_bound和upper_bound,指针运算得出次数。

简易题，直接见代码；

复杂度分析：

库函数就暂且不分析复杂度。

C++代码实现：

// 方法一：
class Solution {
public:
    int getNumberOfK(vector<int>& nums , int k) {
        multiset<int> s;

        for(int x : nums) s.insert(x);

        return s.count(k);
    }
};

// 方法二：
class Solution {
public:
    int getNumberOfK(vector<int>& nums , int k) {
        int cnt = 0;
        for(int x : nums)
            if(x == k)
                cnt++;
        return cnt;
    }
};

// 方法三：
class Solution {
public:
    int getNumberOfK(vector<int>& nums , int k) {

        auto l = lower_bound(nums.begin(), nums.end(), k);
        auto r = upper_bound(nums.begin(), nums.end(), k);

        return r - l;
    }
};