任意删除序列中两个不同的数,众数仍然是众数
不停的删,剩下的最后的数一定是众数
具体实现:
记录一个当前数和出现次数
如果下一个数和当前数不相等,出现次数 - 1
当出现次数变为 0 时,当前数换为下一个数
- #include<cstdio>
- int main()
- {
- int n,sum=0,x,last;
- scanf("%d",&n);
- while(n--)
- {
- scanf("%d",&x);
- if(x==last) sum++;
- else
- {
- sum--;
- if(sum<=0) { sum++; last=x; }
- }
- }
- printf("%d",last);
- }
给你一个 n 个数的数列,其中某个数出现了超过 n div 2 次即众数,请你找出那个数。
第 1 行一个正整数 n。第 2 行 n 个正整数用空格隔开。
一行一个正整数表示那个众数。
5 3 2 3 1 3
3
100% 的数据,n<=500000,数列中每个数 <=maxlongint。
来源: http://www.bubuko.com/infodetail-2446068.html