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，我才意识到问题并没有辣么简单。。。
感觉这道题好神奇。
用到了抵消的思想，对于众数来说，不是众数的数是“非我族类其心必异”
因为众数出现大于n/2次，所以最后剩下的数一定是众数。
具体见代码。
1/* ***********************************************
2Author :111qqz
3Created Time :2016年11月18日 星期五 21时52分27秒
4File Name :code/bzoj/2456.cpp
5************************************************ */
6#include <cstdio>
7int n;
8int main()
9{
10 scanf("%d",&n);
11 int cnt = 0 ;
12 int val;
13 int x;
14 for ( int i = 1 ;i <= n ; i++){
15 scanf("%d",&x);
16 if (cnt==0)
17 {
18 cnt++;
19 val = x;
20 continue;
21 }
22 if (x==val) cnt++; else cnt--;
23 }
24 printf("%d\n",val);
25 return 0;
26}