摩尔投票法——代码实现及注释（力扣169题：找出列表中多数元素）
题源：. - 力扣（LeetCode）
目录
一、摩尔投票法
1.1 关键思想
1.2 时空复杂度
1.3 算法详细步骤
1.4 代码
1.5 算法理解
一、摩尔投票法
摩尔投票法（Boyer–Moore Majority Vote Algorithm），也被称为“多数投票法”，是一种在数组或序列中查找出现次数超过一半的主要元素的算法。这种算法的核心理念为 票数正负抵消 ，主要思想是通过不同元素之间的抵消来找到可能的主要元素候选者，并在最后验证候选者是否真正满足要求。
题目：
1.1 关键思想
让每对不同的数字互相“抵消”，就像投票一样。具体做法是，让两个不同的数字相互“消掉”，直到没有可以抵消的数字为止。最后剩下的数字就很有可能是出现次数最多的数字。
1.2 时空复杂度
该算法的时间复杂度为O(n)，空间复杂度为O(1)。
1.3 算法详细步骤
1、初始化： 票数统计 count = 0 ， 假设目前的候选数是 candidate。
2、循环： 遍历数组 nums 中的每个数字 num 。
当 票数 count 等于 0 ，则假设当前数字 num 是众数。
当 num = candidate ，票数 candidate 自增 1 ,当 num != x 时，票数 candidate 减 1 。
3、返回值： 返回 candidate 即可。
若不好理解，可以去看1.5算法理解
1.4 代码
(1)直接贴在力扣代码处即可（python3）
class Solution:def majorityElement(self, nums: List[int]) -> int:# 如果数组为空，则没有多数元素，直接返回if not nums:return # 初始化计数器为0，候选多数元素为None count = 0candidate = None# 遍历数组中的每一个元素for num in nums:# 如果当前计数器为0，说明之前的候选多数元素已经被抵消完了，此时将当前元素设为新的候选多数元素 if count == 0:candidate = num# 如果当前元素等于候选多数元素，则计数器加1 if num == candidate:count += 1# 如果当前元素不等于候选多数元素，则计数器减1 else:count -= 1# 在遍历结束后，candidate中保存的可能是一个多数元素，但也可能不是（例如，在存在多个出现次数相同的元素且都不超过一半时） candidate_count = 0for num in nums:if num == candidate:candidate_count += 1# 检查candidate是否真的是多数元素if candidate_count > len(nums) / 2:return candidate
1.5 算法理解
（1）假设nums = [3,2,3]，要求返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
开始遍历：
遍历3：
candidate = 3， count = 0 +1
遍历2：
candidate = 3， count = 1 - 1 = 0 （扫描到了和当前候选3不一样的数字2，所以要减去1）
遍历3:
candidate = 3， count = 0 + 1 = 1
返回candidate
（2）假设nums = [1,2,3,2,2,2,5,4,2]，要求返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
开始遍历：
遍历1：
candidate = 1， count = 0 +1
遍历2：
candidate = 1， count = 1 - 1 = 0 （扫描到了和当前候选1不一样的数字2，所以要减去1）
遍历3:
candidate = 3， count = 0 + 1 = 1
遍历2：
candidate = 3， count = 1 - 1 = 0
遍历2：
candidate = 2， count = 0 + 1 = 1（由于前面已经抵消掉count = 0，重新选一个候选数2）
遍历2:
candidate = 2， count = 1 + 1 = 2
遍历5：
candidate = 2， count = 2 - 1 = 1
遍历4：
candidate = 2， count = 1 - 1 = 0
遍历2:
candidate = 2， count = 0 + 1 = 1
返回candidate
如果众数不在前两位，就会有非众数之间的抵消。因为非众数之间内耗，只会进一步使得众数更占优势。 比如众数如果是2，且都在数组尾部，前面其他数字内耗完了，最后使得count大于0的只可能是2。
参考文献：. - 力扣（LeetCode）