bzoj2456: mode

2456: mode

Time Limit: 1 Sec   Memory Limit: 1 MB Submit: 4743   Solved: 1993 [ Submit][ Status][ Discuss]

Description

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

Input

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

Output

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

Sample Input

5 3 2 3 1 3

Sample Output

3

有意思的算法QAQ。。。

因为最多的那个数一定大于n/2

所以我们只需要每一步，如果跟上一个相等就++不想等就等于当前，因为top必然会出现n的一半还多

#include <cstdio>//若是用c++会超内存不知道为什么。。。有毒大概 int main() { int n,k,t=0,x; scanf("%d",&n); int top=0; for(int i=1;i<=n;i++){ scanf("%d",&x); if(x==t) top++; else if(!top){ t=x; top=1; } else top--; } printf("%d\n",t); return 0; }