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次，所以最后剩下的数一定是众数。

具体见代码。

/* ***********************************************
Author :111qqz
Created Time :2016年11月18日 星期五 21时52分27秒
File Name :code/bzoj/2456.cpp
************************************************ */
#include <cstdio>
int n;
int main()
{
    scanf("%d",&n);
    int cnt = 0 ;
    int val;
    int x;
    for ( int i = 1 ;i <= n ; i++){
	scanf("%d",&x);
	if (cnt==0)
	{
	    cnt++;
	    val = x;
	    continue;
	}
	if (x==val) cnt++; else cnt--;
    }
    printf("%d\n",val);
    return 0;
}