摩尔投票算法

定义

摩尔投票算法(Boyer-Moore Majority Vote)由 Robert Boyer 与 J Strother Moore 于 1981 年提出,用于在一次遍历、常数空间内找出序列中出现次数超过一半的元素(多数元素)。

原理

维护一个候选元素和计数器:遍历时若计数为 0,则把当前元素立为候选;若当前元素等于候选则计数加一,否则减一。直观理解是让不同元素两两"抵消",多数元素因数量过半必然留存到最后。若不保证多数元素存在,需再遍历一次验证候选的真实出现次数。

推广

推广版本可找出出现次数超过 n/k 的所有元素:维护 k-1 个候选槽及计数,思想相同,这一形式称 Misra-Gries 算法,是数据流频繁项估计(heavy hitters)的基础,与 Space-Saving、Count-Min Sketch 等流算法密切相关。

应用

海量日志中的高频项粗筛、分布式投票统计、面试算法题(LeetCode 169 多数元素)等。