问题：Majority Element
描述：从数组中，寻找占一半以上的元素。


方法1：计数
时间：O(n)。空间：O(n)
统计数组中每一个元素的个数，存入散列表/二叉查找树。最后遍历散列表/二叉查找树，找到出现次数最多的那个，看看次数是否大于size的1/2。


方法2：Boyer-Moore’s Voting Algorithm
时间：O(n)。空间：O(1)

概述：有一场选举，候选人必须得票半数以上才能获胜。得票信息记录在数组中，例如：[A, B, A, A, B, C]。算法分为两步：

1.选出一个可能的candidate。(如果真的有人得票半数以上，我们得把他选出来)
2.统计这个candidate出现的数目，看看得票是否过半。(看它是不是真的majority element)

第一步的步骤：设置两个变量candidate与count = 0。顺序扫描数组，当count == 0时，将candidate设置为当前元素，count设置为1。当count > 0时，如果当前元素与candidate相同，则count++；如果不同，则count--，若count变成了0，则参考count为0的情况。最终扫描完成后，candidate指向的那个，就有可能是获胜者。

第二步，我们再扫描一次数组，记录candidate的出现次数，看看是否真的过半。如果过半，那candidate就是真的胜者；如果不过半，那说明没有任何人得票过半。

为什么第一步可以选出得票最多的人（如果有的话）呢？可以这么理解。假设这是一场正邪对抗，其中有一位正义使者，其他人都是邪恶联盟的成员。正义使者的力量比所有邪恶联盟成员的力量加起来都要大（即得票过半）。来看以下情况：

    1. 当candidate是正义使者时，如果当前元素为正义使者，这代表他获得了力量（count++）；如果当前元素是邪恶联盟的成员，那么正义使者的力量被抵消（count--）。
    2. 当candidate是邪恶联盟的成员甲时，如果当前元素为他自己，那么他获得了力量（count++）；如果当前元素为正义使者，那么他的力量被抵消（count--）
    3. 当candidate是邪恶联盟的成员甲时，如果当前元素是邪恶联盟的其他成员，那么他们开始内斗（count--），更加无法打败正义使者。

由于正义使者本来力量就比所有邪恶联盟成员的力量加起来都要大，而且邪恶联盟还有可能出现内斗，所以正义使者赢定了，最后candidate == 正义使者，count > 0。所以如果有人得票过半，那么算法第一步一定可以找出他。

那么为什么需要第二步的验证呢？是因为如果没有人得票过半，那么选出的candidate就有可能只是某个运气好的杂鱼而已。假设邪恶联盟里有一个大魔王（与正义使者力量相当）和一个杂鱼：
    [正，正，正，正，魔，魔，魔，杂，杂]
一开始candidate为正义使者，他不断继续力量，最高到4(count == 4)。后来大魔王出现了，正义使者的力量不断被抵消，最后正义使者虽然打败了魔王，却也受了重伤（candidate == 正，count == 1）。最后，被一个杂鱼捡了便宜(最终结果candidate = 杂，count = 1)。可以看出，这个杂鱼连力量最大的人都不是，单纯只是运气好而已。所以我们需要在第二步验证以下，看看candidate是否真的是力量过半的那个。