文档章节

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

o
 osc_wws45aot
发布于 2019/08/20 21:41
字数 324
阅读 3
收藏 0
c++

精选30+云产品,助力企业轻松上云!>>>

【问题】统计一个数字在排序数组中出现的次数。

【思路】首先要清楚这种看似简单的题目,使用直接遍历是可以,但一般不得分,由于题目给出了排序数组,对于排序数组来说,常用的搜索查找方式为二分查找(binary search)。这里有个巧妙的方法,我们并不是去搜索k这个数,而是去搜索k-0.5和k+0.5这两个小数,进而返回待插入的位置!

比如:1 2 2 2 3 4 且k = 2
则,k+0.5会返回3的索引即4,而k-0.5会返回第一个2的索引即1,两者相减得3,即为最后的结果!二分代码如下,只返回begin位置!

class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        return biSearch(data, k+0.5) - biSearch(data, k-0.5);
    }
private:
    int biSearch(vector<int>& data, double num){
        int begin = 0, end = data.size() - 1;
        while(begin <= end){
            int mid = begin + (end - begin) / 2;
            if(data[mid] < num)
                begin = mid + 1;
            else if(data[mid] > num)
                end = mid - 1;
        }
        return begin;
    }
};

另外一个思路直接使用STL中的库函数equal_range来获取与某一个值相等的上下边界,十分好用的!

class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        auto res = equal_range(data.begin(), data.end(), k);
        return res.second - res.first;
    }
};

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

SnailSVN Pro for mac(SVN客户端) v1.9.9

macw为您带来SnailSVN Pro for mac ,SnailSVN Mac版是一款类似于 TortoiseSVN 的 Apache Subversion(SVN)客户端,与 Finder 紧密集成。SnailSVN Mac版允许你从 Finder 的上下文菜单中快速...

单手绕月
5分钟前
0
0
python网络编程(进程与多线程)

multiprocessing模块   由于GIL的存在,python中的多线程其实并不是真正的多线程,如果想要充分地使用多核CPU的资源,在python中大部分情况需要使用多进程。   multiprocessing包是Pytho...

osc_ky74f26k
5分钟前
0
0
CentOS7 redis5.0高可用部署

概述 Redis Sentinel为Redis提供高可用性。Redis Sentinel是一个分布式系统,Sentinel本身设计为在有多个Sentinel进程协同合作的配置中运行。具有多个Sentinel进程进行协作的优点如下: 1、当...

紅顏為君笑
5分钟前
0
0
Ocelot简易教程(四)之请求聚合以及服务发现

上篇文章给大家讲解了Ocelot的一些特性并对路由进行了详细的介绍,今天呢就大家一起来学习下Ocelot的请求聚合以及服务发现功能。希望能对大家有所帮助。 作者:依乐祝 原文地址:https://www...

osc_zo0djpuu
6分钟前
0
0
leetcode63(不同路径 II)--Java语言实现

求: 一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。 现在...

拓拔北海
7分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部