题解 | #数字在升序数组中出现的次数#

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

https://www.nowcoder.com/practice/70610bf967994b22bb1c26f9ae901fa2

基本思路:有序数组,所以可以线性时间复杂度遍历找到该长度。

优化:有序数组中的查找一般都是将线性查找优化为二分搜索。可以转变一下思路,求出该数组中第一个大于等于k的数的下标,以及第一个大于等于k+1,即大于k的数的下标,这两者相减,即为[k, k+1)区间内的数的个数,也即为k的个数。

class Solution {
public:
    int helper(vector<int>& data, int k) {
        int l = 0, r = data.size() - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (data[mid] < k) {
                l = mid + 1;
            }
            else {
                r = mid - 1;
            }
        }
        return l;
    }
    int GetNumberOfK(vector<int> data ,int k) {
        return helper(data, k + 1) - helper(data, k);
    }
};

全部评论

相关推荐

06-26 22:20
门头沟学院 Java
码农索隆:让你把简历发给她,她说一些套话,然后让你加一个人,说这个人给你改简历,然后开始卖课
我的求职精神状态
点赞 评论 收藏
分享
流浪的神仙:无恶意,算法一般好像都得9硕才能干算法太卷啦
点赞 评论 收藏
分享
这算盘打的
程序员小白条:都这样的,都是潜规则,你自己说可以实习一年就行了,实习可以随便跑路的
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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