时间:2021-05-19
【题目要求】给你n个数与n。现在需要你在O(n)的时间内,O(1)的空间内找出出现次数超过50%的数。
【开始胡扯】一开始我看到这道题瞬间蒙蔽(ToT)/~~~(。﹏。*),要是只有O(n)的时间这一条要求,就可以用哈希瞬间解决(也就是用空间换时间),对于O(1)的空间好像很难解决。
【思路一】双重循环,这是解决这道题效率最低的方法了,也就是对每个数都计算它出现的次数,时间复杂度 O(n^2) 直接Out。
【思路二】先排序,让相近的数字排在一起,然后从第一个数开始遍历,现在给一个例子,如:1000012,现在进行排序:0000112,从0开始,设定一个计数器T=0,现在有4个0,则T=4,发现超过了半数,输出0。这个方法就是上一个方法的优化版,Out。
【思路三】就是以空间换时间,哈希的思想,使一个一维数组有两个含义。比如a[x]=y代表x这个数出现了y次,这个方法时间复杂度是O(n),但是空间实在是……不说了(*  ̄︿ ̄) Out
【思路四】先算出概率,选出这些数中最有可能符合要求的几个数,再随机抽取几个。这……还是算了吧。
【思路五】今天的主题,就是所谓的MJRTY算法,也叫多数投票算法,主要思路如下:(这个算法时间复杂度O(n)!空间上不需要额外的储存,所以空间复杂度是O(1)!!!!!!)
如果count==0,则将vote的值设置为数组的当前元素,将count赋值为1;
否则,如果vote和现在数组元素值相同,则count++,反之count–;
重复上述两步,直到扫描完数组。
count赋值为0,再次从头扫描数组,如果数组元素值与vote的值相同则count++,直到扫描完数组为止。
如果此时count的值大于等于n/2,则返回vote的值,反之则返回-1;
以下是代码实现,由于题目保证结果一定存在,所以我们省去了最后一步的检查验证。
关键代码如下所示:
#include<iostream>using namespace std;int len; void Find(int* a, int N) {char candidate;int nTimes, i;for(i=nTimes=0;i<N;i++){if(nTimes==0) candidate=a[i],nTimes=1;else{if(candidate==a[i]) nTimes++;else nTimes--;}}cout<<candidate; }int main(){cin>>len;int a[len];for(int i=0;i<n;i++) cin>>a[i];Find(a,len);system("pause");return 0;}以上所述是小编给大家介绍的出现次数超过一半(50%)的数,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对网站的支持!
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
10月23日消息,日前,《财富》发布了2019未来50强榜单。在50强榜单里,有近一半是新上榜公司,超过80%的公司来自美国或大中华区,超过一半的“
css样式:复制代码代码如下:#login{position:absolute;top:50%;left:50%;margin-left:-标签一半宽度;mar
据调查显示,早在2014年,智能手机就已经占据手机联网数量的91%,微信有10亿多的用户量,超过一半的用户每天打开微信次数超过10次,日活跃度较高,并且微信小程
题目要求为:卡拉兹(Callatz)猜想:对任何一个自然数n,如果它是偶数,那么把它砍掉一半;如果它是奇数,那么把(3n+1)砍掉一半。这样一直反复砍下去,最后
word中有个分栏的作用,但如果内容不太多,分栏的话会出现一半有,一半有空白区域,那如何平均分栏,内容差不多呢?方法也很简单。 步骤 1、打开word文