BZOJ 2456: mode

2456: mode

Time Limit: 1 Sec  Memory Limit: 1 MB
Submit: 7016  Solved: 2750
[Submit][Status][Discuss]

Description

给你一个n个数的数列，其中某个数出现了超过n div 2次即众数，请你找出那个数。

Input

第1行一个正整数n。
第2行n个正整数用空格隔开。

Output

    一行一个正整数表示那个众数。

Sample Input

5
3 2 3 1 3

Sample Output

3

思路：

　　若一个数出现了超过1/2次，那么我们可以发现用它一一抵消一定能剩下这个众数，设两个数now和num，对于每个输入等于num，now++，否则now--，当now=0的时候下次输入替换sum，这样最后剩下的就是答案

#include<cstdio>  
using namespace std;  
int n,a,tot,now;  
int main()  
{  
  scanf("%d",&n);  
  while (n)  
  {  
    n--;  
    scanf("%d",&a);  
    if (now==a) tot++;  
    else  
    {  
      tot--;  
      if (tot<=0) {tot=1;now=a;}  
    }  
  }  
  printf("%d",now);  
  return 0;  
}  

 欢迎来原博客看看>原文链接<