摩尔投票算法
假设有这样一个场景：票选村长，每人可投一票，我们将候选村长从1开始编号，村民们在票上写上候选村长的编号即可完成投票。那么最后统计的票可形成一个整型数组。那么谁是村长呢？票数过半的那个人。
摩尔投票算法可以快速的计算出一个数组中出现次数过半的数即大多数（majority），算法核心思想是同加，异减。我们举个例子。
假设数组是：[1,2,1,1,2,1]。算法步骤如下：
- 1。当前大多数是1，得分置1
- 2。与当前大多数不同，得分 - 1，得分为0，当前大多数 = 1
- 1。与当前大多数不同，得分为0，所以设置当前大多数 1 -> 1，得分置1
- 1。与当前大多数相同，得分 + 1，得分为2，当前大多数 = 1
- 2。与当前大多数不同，得分 - 1 ，得分为1，当前大多数 = 1
- 1。与当前大多数相同，得分 + 1，得分为2，当前大多数 = 1
这意味着1是这个数组中出现次数过半的数。
可以感受得到，算法会保存一个当前大多数，和得分，当遇到一个数不是当前大多数时，得分会减一，当减到0时，大多数会发生改变，并且重置得分为1。
这里需要区分的是，摩尔算法不能用来得到众数（mode），例如数组：[1,1,1,2,2,3,3,4,4]，摩尔算法得出最后的结果应该是4，但4并不是众数，可是显然4也不是大多数，那是因为，大多数是指出现次数过半的数，而这个数组中没有这样的数，所以摩尔算法是是失效的，对于这种情况采取需要重新投票。
出现次数超过一半的数
LeetCode原题：169. Majority Element
这里要求出现次数大于一半，所以直接套用摩尔投票算法即可得到答案。
class Solution(object):
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
a, ca = None, 0
for n in nums:
if a == n : ca += 1
elif ca == 0: a, ca = n, 1
else : ca -= 1
return a出现次数超过数组1/3长
LeetCode原题：229. Majority Element II
还能用摩尔投票法吗？答案当然是要，但是需要变通一下。
需要注意的是出现次数超过数组 $\frac 1 3$ 长的数也许会有多个。
例如数组长度为8时：[1,1,1,2,2,2,3,3]，数组 $\frac 1 3$ 长= $2$ （向下取整），所以1和2都是符合条件的。
但最多只能是2个，证明如下：
证明
设长度为 $n（n > 0）$ 的数组共有 $m$（$ m \ge 3$ ） 种数，它们出现的次数分别为 $a_1, a_2, … a_m（a_i>0,i=1,2,…,m）$ ，且有2种数出现次数大于 $ ⌊\frac n 3⌋$ 。不妨令 $a_1 = a_2 = c + ⌊\frac n 3⌋ $ 其中 $(c >= 1)$。
由定义得： $ a_1 + a_2 + … + a_m = n$ ①
易得： $n-a_1-a_2-a_3 \ge 0$ ②
现假设有第3种数，使得 $a_3 > ⌊\frac n 3⌋ $， 由①得：
$ n-a_1-a_2-a_3 = n - 2 (c + ⌊\frac n 3⌋) - a_3 < n - 2c - 3 ⌊\frac n 3⌋ $
令 $ b = n % 3$， 则有 $ ⌊\frac n 3⌋ = \frac {n-b} 3 $
∴ $n-a_1-a_2-a_3 < n - 2c - 3 ⌊\frac n 3⌋ = b - 2c \le 0$
故有 $ n - (a_1 + a_2 + a_3) < 0$ ，与②矛盾
故不存在第3种出现次数大于 $ ⌊\frac n 3⌋ $ 的数
回到题目
如果我们在使用摩尔算法时，同时记录两个大多数，会怎么样呢？直觉告诉我，这会得到一个大多数，和一个出现次数仅次于大多数的数，但是这两个数不一定会比数组长的1/3大
所以我们得到它们后，还需要检查它们出现的次数是否符合条件。
AC代码：
class Solution(object):
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
a, b, ca, cb, ans = None, None, 0, 0, []
for n in nums:
if n == a: ca += 1
elif n == b: cb += 1
elif ca == 0: a, ca = n, 1
elif cb == 0: b, cb = n, 1
else: ca, cb = ca - 1, cb - 1
ca, cb = 0, 0
for n in nums:
if n == a: ca += 1
elif n == b: cb += 1
if ca > len(nums)/3:
ans.append(a)
if cb > len(nums)/3:
ans.append(b)
return ans
