摩尔多数投票算法

1. 简介

该算法应用的问题原型：在一个集合之中，我们寻找多数元素，该元素重复出现且占到序列元素的一半之上；通过 O(n) 时间复杂度及 O(1) 空间复杂度统计出结果；但是对于该算法有一个问题，即如果一个集合之中，没有占到多数的元素，那么这个第一次遍历的结果就可能是无效的，其给出的元素也是不准确的；所以得再进行遍历一次，去验证给出的元素是否是多数元素；

2. 伪代码

// 给定 nums 集合
初始化 计数器 cnt = 1, 候选人 candidate = nums[0]

循环遍历集合 nums
if (cnt == 0) 
    candidate = 当前 num;
// 如果当前数字是该候选者，则加 1 ，否则 投减票
cnt += candidate == num ? 1 : -1;

return cadidate;

3. 相关链接

练题链接：https://leetcode.cn/problems/majority-element/description/?envType=study-plan-v2&envId=top-interview-150

参考资料：

https://zh.wikipedia.org/wiki/%E5%A4%9A%E6%95%B0%E6%8A%95%E7%A5%A8%E7%AE%97%E6%B3%95

https://www.cs.utexas.edu/~moore/best-ideas/mjrty/