摩尔投票法出自论文Boyer–Moore majority vote algorithm，此算法解决任意多个无序候选人选出票数最多的人。时间复杂度为O(n)，空间复杂度为O(1)。
想象着这样一个画面：会议大厅站满了投票代表，每个都有一个牌子上面写着自己所选的候选人的名字。然后选举意见不合的（所选的候选人不同）两个人，会打一架，并且会同时击倒对方。显而易见，如果一个人拥有的选票比其它所有人加起来的选票还要多的话，这个候选人将会赢得这场“战争”，当混乱结束，最后剩下的那个代表（可能会有多个）将会来自多数人所站的阵营。但是如果所有参加候选人的选票都不是大多数（选票都未超过一半），那么最后站在那的代表（一个人）并不能代表所有的选票的大多数。因此，当某人站到最后时，需要统计他所选的候选人的选票是否超过一半（包括倒下的），来判断选票结果是否有效。
pairing阶段：两个不同选票的人进行对抗，并会同时击倒对方，当剩下的人都是同一阵营，相同选票时，结束。
counting阶段：计数阶段，对最后剩下的进行选票计算统计，判断选票是否超过总票数的一半，选票是否有效。
选票不同就要大干一架，太过粗鲁，这里提供一种更加现代化的文明方式。在场的有个叫onwaier的，他很聪明，他想到一个方法。他用他那犀利人目光扫一遍所有代表们的选票，在脑子记住两件事，当前的候选人的名字cand和他对应的计数k（并不是他的选票数）。起始时，k的值为0，看每个人的选票时，先想想现在k是否为0，如果是0就将cand更新为他将看到的候选人的名字并且将k的值更新为1。观察每个人选票的过程，如果这个人的选票与cand相同，则将k的值加1；否则，将k的值减1。最后的cand可能胜选，还需统计他的总选票数是否超过一半。
//C语言int majorityElement(int *nums, int numsSize);int majorityElement(int *nums, int numsSize){int count = 0, num = 0;for(int i = 0; i < numsSize; i ++){if(count == 0){num = nums[i];count ++;}else{if(num == nums[i]){count ++;}else{count --;}}}return num;}int main(){int testArray[] = {2,4,4,4,4,2,2,4,4,2};int testnum, arrayLen;arrayLen = sizeof(testArray)/sizeof(testArray[0]);testnum = majorityElement(testArray, arrayLen);printf("%d",testnum);}//输出结果为4//Pythonclass Test:def majorityElement(self, nums):count = 0num = 0for i in range(len(nums)):if(count == 0):num = nums[i]count += 1else:if(num == nums[i]):count += 1else:count -= 1return nump = Test()a = [3,3,3,4,4,3,4,4,4]print(p.majorityElement(a))//输出结果为4
原文始发于微信公众号（小雪花安全团队）：摩尔投票法算法分析
- 左青龙
- 微信扫一扫
-
- 右白虎
- 微信扫一扫
-
评论