博耶-摩尔多数投票算法（）,中文常作多数投票算法、摩尔投票算法等，是一种用来寻找一组元素中占多数元素的常数空间复杂度、线性时间复杂度算法。这一算法由和在1981年发表，也是的一种典型算法。
这一算法应用的问题原型是在集合中寻找可能存在的多数元素，这一元素在输入的序列重复出现并占到了序列元素的一半以上；在第一遍遍历之后应该再进行一个遍历以统计第一次算法遍历的结果出现次数，确定其是否为众数；如果一个序列中没有占到多数的元素，那么第一次的结果就可能是无效的随机元素。对于数据流而言，则不太可能在亚线性空间复杂度的情况下中就寻找到出现频率最高的元素；而对于序列，其元素的重复次数也有可能很低。
算法
该算法在其局部变量中存储一个数组元素和一个计数器，计数器初始化为 0。然后对数组进行遍历操作，在遍历到元素 x 的时候：如果计数器为 0，则算法将 x 存储到数组元素变量，并将计数器设置为 1。 否则，它将 x 与存储的元素进行比较，然后递增计数器（如果它们相等）或递减计数器（不相等）。 在此过程结束时，如果数组中存在占多数的元素，则它将是存储的数组元素变量的值。
算法可以用伪代码如下表示：
- 初始化元素并给计数器赋初值
- 对于输入队列中每一个元素：
** 若, 那么 and
** 否则若, 那么
** 否则
- 返回
即便输入序列没有多数元素，这一算法也会返回一个序列元素。然而如果能够进行第二轮遍历，检验返回元素的出现次数，就能判断返回元素是否为多数元素。因此算法需要两次遍历，亚线性空间算法无法通过一次遍历就得出输入中是否存在多数元素。
参见
- 元素唯一性问题，判断序列中该元素唯一
- ，返回多数元素的布尔类型集合
- ，在細胞自動機计算模型中寻找多数元素
参考资料
评论 (0)