给你一个n个数的数列，其中某个数出现了超过n div 2次即众数，请你找出那个数。
本文共 971 字，大约阅读时间需要 3 分钟。
给你一个n个数的数列，其中某个数出现了超过n div 2次即众数，请你找出那个数。
第1行一个正整数n。
第2行n个正整数用空格隔开。一行一个正整数表示那个众数。
100%的数据，n<=500000，数列中每个数<=maxlongint。
zju2132 The Most Frequent Number
题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2456
分析:此题极其诡异，先看内存，1MB，这一点估计就会卡到死吧，然后就是显然不能开数组做，说水题其实也不是很水，怎么做，下面给出一种非常神奇的做法！
题目里定义的众数出现次数超过数组的一半 其他所有数加起来都没它多!
那就我定义一个cnt=1(至少要一个数)和res=0(初始化) 如果下一个数不等于res就抵消掉让cnt-1；当cnt为0时把res赋成下一个数 最后结果就是res，因为剩下没有数能够抵消它！下面给出C语言AC代码：(尽量别去跑C++，耗时耗内存)
1 #include2 int main() 3 { 4 int n; 5 scanf("%d",&n); 6 int res=0,cnt=1,c; 7 for(int i=1;i<=n;i++) 8 { 9 scanf("%d",&c);10 if(c==res)11 cnt++;12 else cnt--;13 if(cnt<=0)14 {15 res=c;16 cnt=1;17 }18 }19 printf("%d",res);20 return 0;21 }
转载地址：http://ynbsx.baihongyu.com/