资讯

精准传达 • 有效沟通

从品牌网站建设到网络营销策划,从策略到执行的一站式服务

求出数组中超过一半的数-创新互联

Tango 是微软亚洲研究院的一个试验项目。研究院的员工和实习生们都很喜欢在 Tango上面交流灌水。传说,Tango 有一大“水王”,他不但喜欢发贴,还会回复其他 ID 发的每个帖子。坊间风闻该“水王”发帖数目超过了帖子总数的一半。如果你有一个当前论坛上所有帖子(包括回帖)的列表,其中帖子作者的 ID 也在表中,你能快速找出这个传说中的 Tango 水王吗?

让客户满意是我们工作的目标,不断超越客户的期望值来自于我们对这个行业的热爱。我们立志把好的技术通过有效、简单的方式提供给客户,将通过不懈努力成为客户在信息化领域值得信任、有价值的长期合作伙伴,公司提供的服务项目有:申请域名网站空间、营销软件、网站建设、宾阳网站维护、网站推广。

思路:首先想到的是一个最直接的方法,我们可以对所有 ID 进行排序。然后再扫描一遍排好序的 ID 列表,统计各个 ID 出现的次数。如果某个 ID 出现的次数超过总数的一半,那么就输出这个 ID。这个算法的时间复杂度为 ON* log2N+ N)。如果 ID 列表已经是有序的,还需要扫描一遍整个列表来统计各个 ID 出现的次数吗?
如果一个 ID 出现的次数超过总数 N的一半。那么,无论水王的 ID 是什么,这个有序的 ID 列表中的第 N/2 项(从 0 开始编号)一定会是这个 ID(读者可以试着证明一下)。省去重新扫描一遍列表, 可以节省一点算法耗费的时间。如果能够迅速定位到列表的某一项 (比如使用数组来存储列表),除去排序的时间复杂度,后处理需要的时间为 O(1)。但上面两种方法都需要先对 ID 列表进行排序,时间复杂度方面没有本质的改进。能否避免排序呢

如果每次删除两个不同的 ID(不管是否包含“水王”的 ID),那么,在剩下的 ID 列表中,“水王”ID 出现的次数仍然超过总数的一半。看到这一点之后, 就可以通过不断重复这个过程,把 ID 列表中的 ID 总数降低(转化为更小的问题),从而得到问题的答案。新的思路,避免了排序这个耗时的步骤,总的时间复杂度只有 ON),且只需要常数的额外内存。

#include
using namespace std;
//类比为一个数组中超过一半的数,求出这个数 
template
T Find(T* a,int size)
{
	T ret=-1;
	int time=0;
	for(int i=0;i
参照:https://github.com/xiaozhi1995/SmartCode/blob/master/20160511702SearchMidNum/main.cpp

另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。


分享题目:求出数组中超过一半的数-创新互联
新闻来源:http://www.cdkjz.cn/article/cseehc.html
多年建站经验

多一份参考,总有益处

联系快上网,免费获得专属《策划方案》及报价

咨询相关问题或预约面谈,可以通过以下方式与我们联系

大客户专线   成都:13518219792   座机:028-86922220