欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数字在排序数组中出现的次数(二分查找法)——剑指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;
    }
};