一个漂亮的Boyer-Moore投票算法.有人知道类似的算法吗?

Question

Boyer Moore多数投票算法采用了一种漂亮的方法，在第一轮中突出显示可能的多数元素，然后在第二轮中检查其有效性。有人知道类似的一类两步算法吗?试着搜索，但找不到。谢谢! !你能分享一下这两种算法吗?

Answer 1

如果你正在寻找Boyer-Moore算法的泛化，这里有一个由Karp-Papadimitriou-Shanker提出的。

该算法寻找"频繁"元素的候选元素，其中"频繁"被定义为重复1/Θ次，对于某些Θ in (0,1)。

算法产生一个1/Θ候选列表，其中一些可能是假阳性，但它从来没有错过一个候选。

算法为1遍算法。
如果允许对数据进行二次传递，则很容易验证哪些候选数据确实是"频繁的"

算法的伪代码(取自我上过的课程):

1. PF = ∅
2. foreach element e∈S {
3.   if PF.hasKey(e) { // increase counter
4.     PF.value(e)++ // of existing elements
5.   }
6.   Else {
7.     PF.insert(e,1) // insert new element
8.     If |PF|== 1/θ { // but if PF is full
9.       Foreach key ∈ PF {
10.        PF.value(k)-- // decrease all counters
11.        if PF.value(k) == 0 { // and remove
12.          PF.remove(k) // elements at 0
13. } } } } }
14. Output PF