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

Posted by 111qqz on Sunday, November 20, 2016

TOC

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,我才意识到问题并没有辣么简单。。。

_001

感觉这道题好神奇。

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

因为众数出现大于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;
}

「真诚赞赏,手留余香」

111qqz的小窝

真诚赞赏,手留余香

使用微信扫描二维码完成支付