剑指offer 55- 数字在排序数组中出现的次数

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

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

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

输出：4

分析：
算法一：用hash
时间复杂度是

class Solution {
public:
    int getNumberOfK(vector<int>& nums , int k) {
        //用hash时间复杂度是O（N）
        unordered_map<int, int> count;
        for(auto x:nums) count[x]++;
        return count[k];
    }
};

算法二：用二分
用两次二分分别找到重复数的左端点和右端点，求其长度即为k重复的次数
时间复杂度是

class Solution {
public:
    int getNumberOfK(vector<int>& nums , int k) {
        
        //二分法 时间复杂度：logn
        if(nums.empty()) return 0;
        int l = 0, r = nums.size()-1;
        while(l < r) {
            int mid = l+r >> 1;
            if(nums[mid]<k) l = mid+1;
            else r = mid;
        }
        if(nums[l] != k) return 0;
        int left = l;
        l = 0, r = nums.size()-1;
        while(l<r) {
            int mid = l+r+1 >> 1;
            if(nums[mid]<=k) l = mid;
            else r = mid-1;
        }
        return r-left+1;
    }
};