小编典典

线性时间投票算法。我不明白

algorithm

当我阅读本文时在数组中找到最常见的条目,建议使用Boyer和Moore的线性时间投票算法

如果您单击该站点的链接,则会逐步说明该算法的工作原理。对于给定的序列,AAACCBBCCCBCC它提供了正确的解决方案。

当我们将指针向前移到元素e上时:

  • 如果计数器为0,则将当前候选项设置为e,并将计数器设置为1。
  • 如果计数器不为0,则根据e是否为当前候选者来递增或递减计数器。

完成后,如果存在多数,则当前候选者为多数元素。

如果我在一张纸上使用此算法AAACCBB作为输入, 建议的候选对象将成为B, 这显然是错误的。

在我看来,有两种可能性

  1. 作者除了从未完全尝试过他们的算法外AAACCBBCCCBCC,完全没有能力,应当场开除 (怀疑
  2. 我显然缺少了一些东西 ,必须从中禁止它,并且再也不允许再次接触涉及逻辑的东西。

注意:这是Niek Sanders提供的该算法的C++实现。我相信他正确地实现了这个想法,因此它有同样的问题(不是吗?)。


阅读 170

收藏
2020-07-28

共1个答案

小编典典

该算法仅在集合占多数时才起作用-超过一半的元素相同。AAACCBB在您的示例中没有这样的多数。最频繁的字母出现3次,字符串长度为7。

2020-07-28