利用好标准库,轻松解决

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

http://www.nowcoder.com/questionTerminal/70610bf967994b22bb1c26f9ae901fa2

利用c++标准库,二分查找,O(logn)复杂度。

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;
    }
};
全部评论
count是顺序查找时间复杂度O(n),lower_bound和upper_bound是针对有序数组,底层是二分查找,时间复杂度O(logn)
1 回复 分享
发布于 2020-04-20 11:32
算法用库函数就没必要叫算法了
点赞 回复 分享
发布于 2021-08-08 15:28
哼我还有同样快速并且更简洁的呢 auto p=equal_range(data.begin(), data.end(), k); return p.second - p.first;
点赞 回复 分享
发布于 2021-05-09 23:17
为什么用int就不对呢
点赞 回复 分享
发布于 2020-12-27 16:20
为啥不直接count(data.begin(),data.end(),k) (手动狗头)
点赞 回复 分享
发布于 2020-04-11 13:08
为什么要用auto不用int
点赞 回复 分享
发布于 2019-10-17 23:16

相关推荐

08-29 19:44
门头沟学院 Java
wish233:很强了,加上这个学历,一点小建议就是可以把你的项目做一个压测,比如说你的RPC,可以对比一下和http相比性能怎么样。还有你的秒杀,一定要自己压测一遍,确保不会出现数据不一致的问题。还有就是对于分布式锁的粒度一定要理清楚,这个很容易被问到。
听劝,我这个简历该怎么改...
点赞 评论 收藏
分享
投递中科曙光等公司10个岗位
点赞 评论 收藏
分享
评论
15
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务