数字在排序数组中出现的次数(二分查找法)——剑指Offer
程序员文章站
2024-03-20 11:59:16
...
题目描述
统计一个数字在排序数组中出现的次数。
题目分析
利用c++标准库,通过二分查找的方法,复杂度为O(logn)。
lower_bound是返回小于等于当前数的下标
而upper_bound只能返回第一个大于当前数的下标
代码
C++代码如下:
class Solution {
public:
int GetNumberOfK(vector<int> data ,int k) {
auto l=lower_bound(data.begin(),data.end(),k);
auto r=upper_bound(data.begin(),data.end(),k);
return r-l;
}
};