多数投票算法

✍ dations ◷ 2025-08-23 08:28:36 #算法

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

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

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

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

相关

  • 深南部深南部(Deep South 或 Lower South),又称为棉花州(Cotton States),也常被译为南方腹地,是美国南部的文化与地理区域名称,与“上南方”(Upper South)相对。深南部并没有统一的定义,一般
  • 重工业重工业为工业的一种下属分类相对于轻工业,通常指钢铁业、石化业这种需要大型生产设备和大量人力的工业,重工业特性是能提供大量工作机会,但是技术难度只属中等,唯一需要的是大量
  • 阿里·哈梅内伊大阿亚图拉赛义德阿里·哈梅内伊(波斯语:آیت‌الله سید علی خامنه‌ای‎;阿塞拜疆语:سید علی حسینی خامنه‌ای/Seyyid Əli Hüseyni Xa
  • 老人痴呆阿尔茨海默病(拉丁语:Morbus Alzheimer、德语:Alzheimer-Krankheit、英语:Alzheimer's disease,缩写:AD),俗称早老性痴呆、老年痴呆,是一种发病进程缓慢、随着时间不断恶化的神经退化
  • 五硫化二锑五硫化二锑是一种锑和硫生成的化合物,不同于三硫化二锑,是一种非整比化合物,为深橙黄色粉末,不溶于水,常用于橡胶工业和制作兽药。可以用全硫代锑酸盐加酸来制备它。但是无法证明
  • 菲利普·诺埃尔-贝克菲利普约翰·诺埃尔-贝克,诺埃尔-贝克男爵(英语:Philip Noel-Baker, Baron Noel-Baker,1889年11月1日-1982年10月8日),英国政治家、外交家、学者、杰出的业余运动员,以解决战争,纠纷
  • 数字视频转换盒数字视频转换盒(英语:set-top box,缩写:STB)是一个连接电视机与外部信号源的设备。它可以将源信号转成电视内容,并在电视机上显示出来。信号可以来自有线电缆、卫星天线、宽带网络
  • 同时估计法同时估计法(Concurrent estimation)是离散事件仿真中使用的技术,用来估计离散事件动态系统下,不同参数设定的效果。例如观察电脑模拟的通讯系统,其缓冲区大小为
  • 朱益濬朱益濬(?-1920年),字辅源,号纯卿,江西莲花县人,清末政治人物。光绪三年(1877年)丁丑科进士,选翰林院庶吉士,散馆改湖南衡州府清泉县知县。官至湖南辰沅永靖道,护理巡抚,辛亥革命后归里。民
  • 波士顿科学波士顿科学 (英语:Boston Scientific)是一家美国医疗器械制造商。1979年6月成立于美国米德尔塞克斯县马尔伯勒市,1992年5月19日在纽约证券交易所成功上市,1997年进入中国,其大中