ZOJ 2132 the most frequent number

Description

Seven (actually six) problems may be somewhat few for a contest. But I am really unable to devise another problem related to Fantasy Game Series. So I make up an very easy problem as the closing problem for this contest.

Given a sequence of numbers A, for a number X if it has the most instances (elements of the same value as X) in A, then X is called one of the most frequent numbers of A. Now a sequence of numbers A of length L is given, and it is assumed that there is a number X which has more than L / 2 instances in A. Apparently X is the only one most frequent number of A. Could you find out X with a very limited memory?

Input

Input contains multiple test cases. Each test case there is one line, which starts with a number L (1 <= L <= 250000), followed by L numbers (-2^31 ~ 2^31-1). Adjacent numbers is separated by a blank space.

Output

There is one line for each test case, which is the only one most frequent number X.

Sample Input

5 2 1 2 3 2 8 3 3 4 4 4 4 3 4

Sample Output

2

4

找出数组中超过半数的那个数，限制了内存大小，可以用map或链表过，但其实有更简单的办法。

#include<iostream>  
#include<algorithm>
#include<cstdio>
#include<string>
using namespace std;
int n, x, a, b;

int main()
{
  while (~scanf("%d", &n))
  {
    for (int i = a = b = 0; i < n; i++)
    {
      scanf("%d", &x);
      if (b == 0) { a = x; b = 1; }
      else if (a == x) b++; else b--;
    }
    printf("%d\n", a);
  }
  return 0;
}