多数投票算法

✍ dations ◷ 2025-11-29 12:43:05 #算法

博耶-摩尔多数投票算法(英语:Boyer–Moore majority vote algorithm),中文常作多数投票算法、摩尔投票算法等,是一种用来寻找一组元素中占多数元素的常数空间级时间复杂度算法。这一算法由罗伯特·S·博耶(英语:Robert S. Boyer)和J·斯特罗瑟·摩尔(英语:J Strother Moore)在1981年发表,也是处理数据流(英语:streaming algorithm)的一种典型算法。

这一算法应用的问题原型是在集合中寻找可能存在的多数元素,这一元素在输入的序列重复出现并占到了序列元素的一半以上;在第一遍遍历之后应该再进行一个遍历以统计第一次算法遍历的结果出现次数,确定其是否为众数;如果一个序列中没有占到多数的元素,那么第一次的结果就可能是无效的随机元素。对于数据流而言,则不太可能在亚线性空间复杂度的情况下中就寻找到出现频率最高的元素;而对于序列,其元素的重复次数也有可能很低。

算法可以用伪代码如下表示:

即便输入序列没有多数元素,这一算法也会返回一个序列元素。然而如果能够进行第二轮遍历,检验返回元素的出现次数,就能判断返回元素是否为多数元素。因此算法需要两次遍历,亚线性空间算法无法通过一次遍历就得出输入中是否存在多数元素。

相关

  • 威廉·蒂莫西·高尔斯威廉·蒂莫西·高尔斯爵士,KBE,FRS(英语:Sir William Timothy Gowers,1963年11月20日-),英国数学家、作家,1998年菲尔兹奖得主。高尔斯早年受教于英格兰剑桥郡的国王学院(英语:King's C
  • 字母间距字符间距(英语:Letterspacing,也称英语:Tracking)简称字距,在字体排版学中指的是字符之间的空隙,该属性影响文本行或文本块的密度。字符间距容易与字距调整混淆。CSS(层叠样式表)中,wo
  • 二酸甘油酯二酸甘油酯(英语:diacylglycerol,或称为甘油二酯,英语:diglyceride,二酰基甘油,缩写DAG)是一类由两个脂肪酸链和一个甘油分子通过酯键形成的甘油酯。二酸甘油酯有两种类型:1,2-二酸甘
  • 台语文台语白话文,或称为台湾话文、台语文、台文,是一种符合并融合台湾话语法、本身词汇以及外来词汇的书面文系统,主要流行于台湾、福建、广东一带、新加坡以及马来西亚。传统的台语
  • 王中之王王中之王(古希腊语:βασιλευς των βασιλευοντων;英语:King of Kings),又译为诸王之王、万王之王,源自古代近东地区的帝国统治者称号,大致相当于皇帝。在基督
  • 何塞·奥特嘉·伊·加塞特何塞·奥特嘉·伊·加塞特(José Ortega y Gasset,1883年5月9日-1955年10月18日),简称奥特嘉,是一位西班牙的哲学家、报业从业人员及评论家。其哲学思想主要是存在主义、历史哲学
  • 卡洛斯三世 (西班牙)卡洛斯三世(西班牙语:Carlos III,1716年1月20日—1788年12月14日)波旁王朝的西班牙国王(1759年—1788年在位),即位前封号为帕尔马公爵(称卡洛一世,1731年—1735年)。他也是那不勒斯国
  • 灰色软件灰色软件(Greyware或Grayware),又称“信息安全威胁程序”这个名词是由趋势科技发明,用来泛指所有不被认为是电脑病毒或木马程序,但会对你所在机构的网络上所使用的电脑的性能造成
  • 行星 (占星术)占星术中的行星有着别于现代天文对于什么是行星解释之含意。在望远镜问世的时代以前,夜空被认为由两个相似的构成要素组成著:恒星,相对于其他星体祂是一动也不动得,加上“游星”
  • 朝日温泉坐标:22°38′12″N 121°30′17″E / 22.636802°N 121.504617°E / 22.636802; 121.504617朝日温泉,原称作滚水坪(台湾话:.mw-parser-output .sans-serif{font-family:-apple-