题目描述

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

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

样例

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

输出：4

算法

(二分) $O(n^2)$

1. 二分 k 出现的左端点
2. 如果二分的结果不是 k，说明数组中没有 k，返回 0
3. 否则继续二分 k 出现的右端点
4. 出现次数就是左端点和右端点之间的元素个数

时间复杂度

二分中只会迭代 logn 次，所以时间复杂度为 $O(logn)$

C++ 代码

class Solution {
public:
    int getNumberOfK(vector<int>& nums , int k) {
        if (nums.empty()) return 0;

        // 二分左端点
        int l = 0, r = nums.size() - 1;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (nums[mid] >= k) r = mid;
            else l = mid + 1;
        }

        // 如果二分结果不是 k，说明数组中没有 k
        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;
    }
};