一个漂亮的算法- Boyer-Moore投票算法。有谁知道类似的算法吗？
一个漂亮的算法- Boyer-Moore投票算法。有谁知道类似的算法吗？
提问于 2015-07-06 19:45:32
Boyer Moore多数投票算法采用了一种漂亮的方法，在第一次投票中突出可能的多数元素，然后在第二次投票中检查其有效性。有谁知道类似的2种传球算法吗？试着搜索却找不到。谢谢!！你能分享这两种算法中的一些吗？
回答 1
Stack Overflow用户
回答已采纳
发布于 2015-07-06 19:52:34
如果您正在寻找Boyer算法的推广，那么有一个是由卡普-帕帕迪米特里欧-尚克提出的。
该算法是为“频繁”元素寻找候选项，其中“频繁”被定义为重复1/Θ时间，用于某些Θ \in (0,1)。
该算法生成一个1/Θ候选列表，其中一些可能是假阳性，但它永远不会遗漏一个候选人。
该算法为1通算法。
如果您允许第二次传递数据，那么很容易验证哪些候选人确实“频繁”。
该算法的伪代码(取自课程 I TAed)：
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页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/31254347
复制相关文章
相似问题
腾讯云开发者
