2456: mode
Time Limit: 1 SecDescription
给你一个n个数的数列,其中某个数出现了超过n div 2次即众数,请你找出那个数。
Input
第1行一个正整数n。
第2行n个正整数用空格隔开。
Output
一行一个正整数表示那个众数。
Sample Input
5
3 2 3 1 3
3 2 3 1 3
Sample Output
3
HINT
100%的数据,n<=500000,数列中每个数<=maxlongint。
zju2132 The Most Frequent Number
【题解】
FJOI2013SC讲过,就是用两个变量即可。
这样去想:
有几个小人打仗,同族(数字相同)的一个小人可以和另外一族的一个小人同归于尽,那么题目说众数个数大于n/2,那么我们能保证,剩下来的小人一定是众数(可以剩下多个同族小人)【注意内存限制1MB】
一次AC好爽,好久没有这么爽了。
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 #include <stdio.h> 2 using namespace std; 3 int main() { 4 int n; 5 scanf("%d",&n); 6 int tot=0,a,now; 7 bool f=1; 8 for (int i=1;i<=n;++i) { 9 scanf("%d",&a); 10 if (f) { 11 f=0; 12 tot++; 13 now=a; 14 } else { 15 if (a==now) tot++; 16 else { 17 tot--; 18 if(tot<0) { 19 f=1; 20 tot=0; 21 } 22 } 23 } 24 } 25 printf("%d ",now); 26 return 0; 27 }