2456: mode

Time Limit: 1 Sec  Memory Limit: 1 MB

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。

zju2132 The Most Frequent Number

Source

---

　　这道题我开始以为极水，读进来sort，统计出结果即可。但是……为什么Memory Limit: 1 MB！！！

　　于是我们必须边读边算，使用O（1）的空间，做O（n）的事情。

　　怎么办呢？看起来很不现实啊！百思不得其解，于是再读题，发现这个众数有保障：“出现了超过n div 2次”。首先可以发现，这样的结果一定是唯一的。即，如果对于一个数，序列中与其相同的数即为+1，否则计为-1，那么经过统计过后，若序列总和为一正数，则其为众数。

　　于是我们进一步深入，可以进一步约简这个过程，用hzwer大大的话就是：

　　把每个数和一个与它不同的数相抵消，由于要求的数出现了超过n div 2次，那么最后剩下的就是答案。

　　代码很短，但我写了读优。

　　

1 /**************************************************************  2     Problem: 2456  3     User: Doggu  4     Language: C++  5     Result: Accepted  6     Time:212 ms  7     Memory:820 kb  8 ****************************************************************/ 9   10 #include 
       
         11 #include 
        
          12 template
         
          inline void readin(T &res) { 13     static char ch; 14     while((ch=getchar())<'0'||ch>'9'); 15     res=ch-48;while((ch=getchar())>='0'&&ch<='9')res=(res<<1)+(res<<3)+ch-48; 16 } 17 int n, tot; 18 long long aa, num; 19 int main() { 20     readin(n); 21     for( int i = 1; i <= n; i++ ) { 22         readin(aa); 23         if(aa==num) tot++; 24         else tot--; 25         if(tot<=0) { 26             tot=1; 27             num=aa; 28         } 29     } 30     printf("%lld\n",num); 31     return 0; 32 }