bzoj 2456: mode (O(1)找到出现次数大于n/2的数)

2456: mode

Time Limit: 1 Sec  Memory Limit: 1 MB
Submit: 3887  Solved: 1636
[Submit][Status][Discuss]

Description

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

Input

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

Output

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

Sample Input

5
3 2 3 1 3

Sample Output

3

HINT

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

zju2132 The Most Frequent Number

思路:一开始没注意空间限制…不过为毛是TLE。。。以至于最后什么都不干也TLE,我才意识到问题并没有辣么简单。。。

%e9%80%89%e5%8c%ba_001

 

感觉这道题好神奇。

用到了抵消的思想,对于众数来说,不是众数的数是“非我族类其心必异”

因为众数出现大于n/2次,所以最后剩下的数一定是众数。

具体见代码。

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz