题目

传送门= ̄ω ̄=

时间限制: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;
}
分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

0 条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注