二分搜索

k的个数 = 第一个大于k的索引号 - 第一个大于等于k的索引号
这两个索引号都可以用二分搜索得到.

时间复杂度

用了两次二分搜索, 因此, 时间复杂度是: O(log(n))

Python 代码

from bisect import bisect_left, bisect_right

class Solution(object):
    def getNumberOfK(self, nums, k):
        """
        :type nums: list[int]
        :type k: int
        :rtype: int
        """
        return bisect_right(nums, k) - bisect_left(nums, k)

C++ 代码

class Solution {
public:
    int getNumberOfK(vector<int>& nums, int k) {
        return upper_bound(nums.begin(), nums.end(), k) - lower_bound(nums.begin(), nums.end(), k);
    }
};

借助equal_range一个函数搞定.

class Solution {
public:
    int getNumberOfK(vector<int>& nums, int k) {
        auto p{ equal_range(nums.begin(), nums.end(), k) };
        return p.second - p.first;
    }
};