摩爾投票法又叫多數(shù)投票法。

解決的問題
如何在任意多的候選人中，選出獲得票數(shù)最多的那個

算法包括兩個階段

1. 對抗階段：分屬兩個候選人的票數(shù)兩兩對抗抵消
2. 計數(shù)極端：計算對抗結(jié)果中最后留下的候選人票數(shù)是否有效

代碼框架

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

復(fù)雜度
線性時間復(fù)雜度，常數(shù)級空間復(fù)雜度

題目
Leetcode #169 多數(shù)元素
Leetcode #面試題 17.10 主要元素
Leetcode #229 求眾數(shù)II

總結(jié)
1. 如果至多選一個代表，那么他的票數(shù)要至少超過1/2的票數(shù)
2. 如果至多選兩個代表，票數(shù)至少要超過1/3的票數(shù)
2. 如果至多選m個代表，那他們的票數(shù)至少要超過1/(m+1)