【BZOJ2456】mode（主元素问题）

problem

• 给你一个n个数的数列
• 找出其中出现超过n/2次的数

solution

1、既然众数出现了超过了n/2次，那么任意删除序列中的两个不同的数，众数在新序列中出现的次数也一定会超过n/2次。

2、所以我们就维护一个计数。碰到自己就累加，反之去掉，为0时就用当前读入更新数的值。（注意初始值，此时未读入第一个数，多以一定会减去1，所以cnt先赋成1。

3、！！！看内存，1MB，数组？不止是数组。。。using namespace std加了都会MLE。。。

codes

#include<cstdio>
int main(){
    int n;  scanf("%d", &n);
    int ans=-1, cnt = 1;
    while(n--){
        int x;  scanf("%d", &x);
        if(x == ans)cnt++;
        else cnt--;
        if(cnt == 0){
            ans = x;
            cnt = 1;
        }
    }
    printf("%d\n", ans);
    return 0;
}
  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/80480885