题目

传送门＝￣ω￣＝

时间限制：1s 空间限制：1MB

题目描述

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

输入格式

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

输出格式

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

样例输入

5
3 2 3 1 3

样例输出

3

提示

100% 的数据，n<=500000，数列中每个数<=maxlongint。

zju2132 The Most Frequent Number

题目来源

鸣谢 黄祎程

题解

一眼看过去——水啊，搞个 pb_dsのcc_hash_tab！

交完——果断 MLE。

一看——空间大小：1M……

经过瞬间的反应，想出了只要开 4 个变量的 O(n) 做法，果断写上。

。。。还 MLE……

无语，看 Discuss——不能开 iostream……

何况我还写了 bits/stdc++！

删掉，改成 cstdio。。。

AC 了。。。

思路：每次读入一个数字。。。然后设当前出现最多的数字是 k，如果当前这个数字不等于 k，则让当前这个数字去抵消 k。

具体做法见代码。

#include <cstdio>
typedef long long LL;
LL n,tot,j,k;
int main()
{
    scanf("%lld",&n);
    for(LL i=1;i<=n;i++)
    {
        scanf("%lld",&k);
        if(j==k){tot++;continue;}
        if(tot)tot--;else j=k,tot=1;
    }
    printf("%lld",j);
    return 0;
}