Boyer–Moore majority vote algorithm

发表于 更新于 分类于 ，

简介

博耶-摩尔多数投票算法(Boyer–Moore majority vote algorithm)，是用来求取众数的一种常数空间复杂度的算法。所谓众数，就是数组中数量超过总数组长度一般的元素，也被称为多数元素、主要元素。

思想

两次扫描，第一次得到一个候选元素，第二次判断候选元素是否是我们所需的众数。

第一次扫描

指定一个元素为候选元素candidate（可为任意数），再选定一个变量count来进行计数,然后依次扫描，对于数组中每一个元素，首先判断count是否为0，若为0，则把candidate设置为当前元素。之后判断candidate是否与当前元素相等，若相等则count+=1，否则count-=1。

第二次扫描

第二次扫描统计可能是多数元素出现的次数，从而断定它是不是多数元素。由于最后的候选元素可能不是多数元素，因此需要进行第二次扫描判定。如[1,5,3,4,2,2,2]最后存留候选元素为2，count值为2，但是其不是多数元素。

End

此算法需要两次遍历，亚线性空间算法无法通过一次遍历就得出输入中是否存在多数元素。如Graham Cormode所言：no algorithm can correctly distinguish the cases when an item is just above or just below the threshold in a single pass without using a large amount of space