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.

the first line contains the number of kolyan‘s banknotes n (1 ≤ n ≤ 500000). in the next n lines, the values k of these banknotes are given (0 ≤ k ≤ 109).

more than half of them are the same.

output the most common value.

input

output

又是一個新的算法，原來可以這樣查找的。

我的一句話了解的思想：

計算可以抵消的數量，那麼如果一個數出現的次數超過半那麼最終這個數肯定不會被抵消完。

這個思想叫 moore’s voting algorithm

有了這個思想武器之後，程式就可以寫的很簡單，可以很清楚看到怎麼實作的，

參考資料可以看：

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