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

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

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);
    }
};

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-01 17:13
想去,但是听说加班强度实在难崩,所以拒绝了,现在有点心梗对面hr感觉也是实习生,打电话的时候怪紧张的,但是感觉人很好嘞
水中水之下水道的鼠鼠:哥们这不先去体验一下,不行再跑呗,大不了混个实习经历(有更好的转正offer就当我没说)
点赞 评论 收藏
分享
07-02 10:44
门头沟学院 C++
码农索隆:太实诚了,告诉hr,你能实习至少6个月
点赞 评论 收藏
分享
06-12 17:46
门头沟学院 Java
运营你豪哥:来说重点: ​1.项目前置,时间倒序。​​ 2.​项目描述强化结果与量化效果(STAR原则里的R)。​​ ​3.个人技能精炼,明确掌握程度,突出核心。​​ ​4.增加强有力开头的个人总结部分。​​ 5.​优化教育背景(成绩排名)、合并奖项与活动。​​
听劝,我这个简历该怎么改...
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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