首页 > 代码库 > BZOJ2456: mode(trick乱搞QWQ)
BZOJ2456: mode(trick乱搞QWQ)
Description
给你一个n个数的数列，其中某个数出现了超过n div 2次即众数，请你找出那个数。
Input
第1行一个正整数n。
第2行n个正整数用空格隔开。
Output
一行一个正整数表示那个众数。
Sample Input
5
3 2 3 1 3
Sample Output
3
HINT
100%的数据，n<=500000，数列中每个数<=maxlongint。
Solve:
首先,鬼知道我bits...在BZOJ被MLE了。。。
然后,如果有众数,那么这个数出现的次数一定>n/2,所以这有个神做法就是直接记录数和次数,最后留下的一定是众数。
Code:
1 #include <cstdio> 2 int n , ans , ci = 0; 3 int main() 4 { 5 scanf("%d" , &n); 6 while(n--) 7 { 8 int x; 9 scanf("%d" , &x);10 if(ci == 0)11 {12 ans = x;13 ci = 1;14 continue;15 }16 if(ans == x) ++ci;17 else --ci;18 }19 printf("%d\n" , ans);20 }
BZOJ2456: mode(trick乱搞QWQ)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。