摩尔投票法算法分析

admin 2022年6月26日02:05:44评论34 views字数 1546阅读5分9秒阅读模式

摩尔投票法出自论文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可能胜选,还需统计他的总选票数是否超过一半。

算法应用:
        题目名称:多数元素
        给定一个大小为 n 的数组 nums ,返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的,并且给定的数组总是存在多数元素。
//C语言#include<stdio.h>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 = 0 num = 0 for i in range(len(nums)): if(count == 0): num = nums[i] count += 1 else: if(num == nums[i]): count += 1 else: count -= 1 return nump = Test()a = [3,3,3,4,4,3,4,4,4]print(p.majorityElement(a))//输出结果为4

原文始发于微信公众号(小雪花安全团队):摩尔投票法算法分析

  • 左青龙
  • 微信扫一扫
  • weinxin
  • 右白虎
  • 微信扫一扫
  • weinxin
admin
  • 本文由 发表于 2022年6月26日02:05:44
  • 转载请保留本文链接(CN-SEC中文网:感谢原作者辛苦付出):
                   摩尔投票法算法分析https://cn-sec.com/archives/1144081.html

发表评论

匿名网友 填写信息