题目

传送门= ̄ω ̄=

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

题目描述

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

输入格式

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

输出格式

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

样例输入

样例输出

提示

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。

具体做法见代码。