洛谷-2397 yyy loves Maths VI (mode)

mkopvec

于 2019-10-30 13:38:22 发布

阅读量152

点赞数

分类专栏：算法题

本文链接：https://blog.csdn.net/mkopvec/article/details/102817430

版权

算法题专栏收录该内容

311 篇文章

订阅专栏

本文介绍了一种在极小的空间限制下寻找众数的方法——摩尔投票法。该算法能在1s内处理多达2000000个整数，且每个数小于2^31-1。通过初始化计数器和候选众数，遍历数组更新计数器，最终找到出现次数超过一半的众数。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目描述
他让redbag找众数
他还特意表示,这个众数出现次数超过了一半
一共n个数,而且保证有
n<=2000000
而且每个数< $2^{31}-1$
输入格式
第一行一个整数n
第二行n个整数
输出格式
一行,这个众数

输入输出样例
输入 #1
5
2 3 3 3 3

输出 #1
3

说明/提示
时间限制 1s
空间限制 3.5M(你没看错3.5M)
有人想水过,但我告诉你这空间是不够的

解释：据说叫摩尔投票法，如果众数表示1，其他表示-1，那么加起来肯定大于0…这么极端的情况成立，那么那么如果读入的数和存的数不一样的话我们-1，否则+1，最后一定是众数

#include<iostream>
using namespace std;
int n=0,mk=0,c33=0;
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1,a=0;i<=n;i++){
        cin>>a;
        if(c33==0) mk=a;
        if(mk==a) c33++;
        else c33--;
    }
    cout<<mk<<endl;
    return 0;
}