题目大意

给$n$个数，找众数。

其中某个数出现了超过$\frac{n}{2}$次即众数

空间限制为$1MB$

数据范围

$n\leqslant 500000,数列中每个数\leqslant maxlongint$

题解

这个空间限制注定不能开数组

不用开数组，扫一遍就可以了，每次把不同的数消去，最后剩下的就是众数

假设当前认为众数为$x$，数量为$y$，那么$y>\left\lfloor\frac{n}{2}\right\rfloor$，则$x$无论和多少个数消去，$y$都不会低于0，所以最后剩下的总会是$x$

程序

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define For(i,l,r) for(int i=l;i<=r;i++)
using namespace std;

int now,tot,n,x;

int main(){
    scanf("%d",&n);
    For(i,1,n){
        scanf("%d",&x);
        if (now==x) tot++;
        else if (--tot<=0){tot=1;now=x;}
    }
    printf("%d\n",now);
    return 0;
}