本文主要是介绍Boyer-Moore 投票算法小析，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
今日get到摩尔投票算法，时间和空间复杂度都得到了最优的结果，觉得非常经典，在此记录，以备今后查阅，同时希望对和我一样的初学者起到抛砖引玉的效果。
CiterSeerX上论文链接：
https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.56.3439
摩尔投票算法也可以叫做多数投票算法(Boyer–Moore majority vote algorithm)。
查阅相关技术博客，有大神做了如下解释：
想象着这样一个画面：会议大厅站满了投票代表，每个都有一个牌子上面写着自己所选的候选人的名字。然后选举意见不合的（所选的候选人不同）两个人，会打一架，并且会同时击倒对方。显而易见，如果一个人拥有的选票比其它所有人加起来的选票还要多的话，这个候选人将会赢得这场“战争”，当混乱结束，最后剩下的那个代表（可能会有多个）将会来自多数人所站的阵营。但是如果所有参加候选人的选票都不是大多数（选票都未超过一半），那么最后站在那的代表（一个人）并不能代表所有的选票的大多数。因此，当某人站到最后时，需要统计他所选的候选人的选票是否超过一半（包括倒下的），来判断选票结果是否有效。
算法步骤：
1、pairing阶段：2个不同选择的人(此处为选票)，此两票作废，直到数据集中只剩下相同选择的。
2、counting阶段：计数阶段，对上一步剩下的那种选择，在全部数据集上统计总数。判断是否超过数据集长度的一半，超过选票有效，不超过选票无效。
伪代码：
| initialize an element m and a counter i with i =0 |
| For each element x of the total set: |
| if i =0,then assign m=x and i=1 |
| else if m=x,the assign i =i+1 |
| else assign i = i-1 |
| Return m |
Java代码示例（算法官方给出的示例代码段）:
public int majorityElement(int[] nums) {int candidate =-1;int count =0;for(int num:nums){if(count == 0){candidate = num;}if(candidate ==num ){count +=1;}else{count -=1;}}count =0;int n = nums.length;for(int num:nums){if(num == candidate){count+=1;}}return 2*count>n?candidate:-1;}时间复杂度：O(n)，n 为数组长度。
空间复杂度：O(1)，存储常数的额外空间即可。
在此对各位大神的思路分享深表感谢，受益匪浅。
参考文献：
《摩尔投票法(Boyer–Moore majority vote algorithm)》
https://mp.weixin.qq.com/s/-mUH4hySFrcpKaeDotBlFw
这篇关于Boyer-Moore 投票算法小析的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
