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

题目描述

Input:
nums = 1, 2, 3, 3, 3, 3, 4, 6
K = 3

Output:
4

解题思路

#include <unordered_map>
class Solution {
public:
    //二分
    int getNumberOfK(vector<int>& nums , int k) {
        if(nums.empty()) return 0;
        //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;
        }
        //此时找到值为k的左端点 l = r
        if(nums[l] != k) return 0; //判断是否存在k
        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;
    }
    
    //hash On
    int getNumberOfK1(vector<int>& nums , int k) {
        unordered_map<int, int> hash;
        for(auto x : nums)
        {
            hash[x] ++;
        }
        return hash[k];
    }
};