摩尔投票法的基本问题
给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。假设该数组中必然存在多数元素
这是leetcode169. 多数元素
最常规的思路是，遍历+计数，但这样我们需要维护一个哈希表或者字典。于是我们看看摩尔投票法能发挥什么作用
摩尔投票法的原理
5个字：1比1火拼
我们形象地将数组中的不同元素视为不同国家，各国的人数等于对应元素的个数。如[1,2,0,2,4,2,3,2,1,2,2]，视为国0，国1，国2（众数国），国3，国4，人数分别为1，2，6，1，1。我们在这些国家间燃起战火，让它们相互乱战1比1火拼，最坏的情况就是其他国合众连横合起来打你众数国，显然这就是看谁人多呗，人数最多的国2会获胜。这就是摩尔投票法
维护2个变量——存活人数和存活元素。依次扫描数组中的元素，如果当前扫描到的元素与上一扫描元素相同，说明属于同一势力，存活人数+1；如果当前扫描到的元素与上一扫描元素不同，则两两火拼，存活人数-1。当扫描结束后，存活元素存放的值就是这个多数元素
class Solution:
def majorityElement(self, nums: List[int]) -> int:
if nums:
count = 0
ele = 0
for num in nums:
if count == 0:
ele = num
if num == ele:
count += 1
else:
count -= 1
return ele
进阶
思考：能用摩尔投票解决找出数组中出现次数大于1/3长度的数字吗？（假设一定存在至少一个这样的数，当然，至多不超过两个）
分析：
在上面使用摩尔投票法找出出现次数大于1/2长度的众数中，我们可以看到在最坏情况下，每一个众数都抱着一个其他的数同归于尽，最后才能够以量多取胜
以此类推，当试图使用摩尔投票法找出出现次数大于1/3长度的数时，需要3个不同的数一组同归于尽。最坏的情况是，一直都是国家X的一个人拼掉其他两个国家各一人，若国X最后有人剩下，则为所求，代码如下：
def vote(nums):
m,n = 0,0
cm,cn = 0,0
for i in nums:
# 先判断当前扫描到的数是否与m或n相等
if i == m: cm += 1
elif i == n: cn += 1
# 不等，再判断有没有计数为0的
elif cm == 0: m = i; cm += 1
elif cn == 0: n = i; cn += 1
# 否则就是遇到了第三个数，计数都减1
else: cm -= 1; cn -= 1
print('当前遍历至 %s' % i)
print('m is %s, m数量是%s; n is %s, n数量是%s\n' % (m, cm, n, cn))
return m,n
那么这样就全对了吗？非也
诚然，返回的m, n中至少有一个确实满足要求，但另一个就不见得了。举个例子，nums = [1,2,3,1,2,3,2,4]，执行上面的代码，返回是(4, 2)，显然4是不对的。看一下打印日志：
当前遍历至 1
m is 1, m数量是1; n is 0, n数量是0当前遍历至 2
m is 1, m数量是1; n is 2, n数量是1当前遍历至 3
m is 1, m数量是0; n is 2, n数量是0当前遍历至 1
m is 1, m数量是1; n is 2, n数量是0当前遍历至 2
m is 1, m数量是1; n is 2, n数量是1当前遍历至 3
m is 1, m数量是0; n is 2, n数量是0当前遍历至 2
m is 1, m数量是0; n is 2, n数量是1当前遍历至 4
m is 4, m数量是1; n is 2, n数量是1
我们可以看到，前面2组[1,2,3]都互相火拼掉了，最后剩下2和4
2属于一直都在战斗然后活下来的国家，就是我们要求的数；但4从头到尾没参加过一次战斗，纯粹就是坐收渔翁之利苟到最后
因此，1/2与1/3的差别就在于，是否“每个国家都加入了战斗”。只有确保每个国家都加入了战斗，活下来那个才是人多的，而不是苟活的！
因此，我们要检查得到的这两个数，再遍历一次，统计它们出现的次数。。。
class Solution:
def majorityElement(self, nums: List[int]) -> List[int]:
res = list()
m, n = 0, 0
cm, cn = 0, 0
for i in nums:
if i == m:
cm += 1
elif i == n:
cn += 1
elif cm == 0:
m = i
cm += 1
elif cn == 0:
n = i
cn += 1
else:
cm -= 1
cn -= 1
# 再次遍历检验
cm = cn = 0
for i in nums:
if m == i:
cm += 1
elif n == i:
cn += 1
# print(m, n)
# print(cm, cn)
if cm >= len(nums)//3 + 1:
res.append(m)
if cn >= len(nums)//3 + 1:
res.append(n)
return res
