摩尔投票法

摩尔投票法又叫多数投票法。

解决的问题
如何在任意多的候选人中，选出获得票数最多的那个

算法包括两个阶段

1. 对抗阶段：分属两个候选人的票数两两对抗抵消
2. 计数极端：计算对抗结果中最后留下的候选人票数是否有效

代码框架

for n in nums:
    if count == 0:
        major = n
    if n == major:
        count++
    else count--

复杂度
线性时间复杂度，常数级空间复杂度

题目
Leetcode #169 多数元素
Leetcode #面试题 17.10 主要元素
Leetcode #229 求众数II

总结
1. 如果至多选一个代表，那么他的票数要至少超过1/2的票数
2. 如果至多选两个代表，票数至少要超过1/3的票数
2. 如果至多选m个代表，那他们的票数至少要超过1/(m+1)