当我阅读本文时在数组中找到最常见的条目,建议使用Boyer和Moore的线性时间投票算法。
如果您单击该站点的链接,则会逐步说明该算法的工作原理。对于给定的序列,AAACCBBCCCBCC它提供了正确的解决方案。
AAACCBBCCCBCC
当我们将指针向前移到元素e上时: 如果计数器为0,则将当前候选项设置为e,并将计数器设置为1。 如果计数器不为0,则根据e是否为当前候选者来递增或递减计数器。 完成后,如果存在多数,则当前候选者为多数元素。
当我们将指针向前移到元素e上时:
完成后,如果存在多数,则当前候选者为多数元素。
如果我在一张纸上使用此算法AAACCBB作为输入, 建议的候选对象将成为B, 这显然是错误的。
AAACCBB
在我看来,有两种可能性
注意:这是Niek Sanders提供的该算法的C++实现。我相信他正确地实现了这个想法,因此它有同样的问题(不是吗?)。
该算法仅在集合占多数时才起作用-超过一半的元素相同。AAACCBB在您的示例中没有这样的多数。最频繁的字母出现3次,字符串长度为7。