题目

传送门= ̄ω ̄=

时间限制: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

发表评论

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

你是机器人吗? =。= *