Timus 1510. Order 找到出现次数过半的数

A New Russian Kolyan likes two things: money and order. Kolyan has lots of money, but there is no order in it. One beautiful morning Kolyan understood that he couldn't stand this any longer and decided to establish order in his money. He told his faithful mates to fetch the money from an underground depository, and soon his big room was filled up with red, green, and blue banknotes. Kolyan looked with disgust at this terrible mess. Now he wants to leave in his depository only banknotes of the same value and to give the rest of the money to the poor. He knows exactly that more than half banknotes have the same value. But in this mess it is impossible to understand which banknote is the most common.

Input

The first line contains the number of Kolyan's banknotesN(1 ≤N≤ 500000). In the nextNlines, the valuesKof these banknotes are given (0 ≤K≤ 109). More than half of them are the same.

Output

Output the most common value.

Sample

input output

5 3 3 2 2 3	3

又是一个新的算法，原来可以这样查找的。

我的一句话理解的思想：

计算可以抵消的数量，那么如果一个数出现的次数超过半那么最终这个数肯定不会被抵消完。

这个思想叫Moore’s Voting Algorithm

有了这个思想武器之后，程序就可以写的很简单，可以很清楚看到怎么实现的，

参考资料可以看：

http://www.geeksforgeeks.org/majority-element/

#include <iostream>
using namespace std;

void main()
{
	int n = 0, a = 0, majority = 0, c = 1;
	cin>>n>>majority;
	while (--n)
	{
		cin>>a;
		if (majority == a) c++;
		else c--;
		if (0 == c) 
		{
			majority = a;
			c = 1;
		}
	}
	cout<<majority;
}