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

Question

当我读到这个(查找数组中最常见的条目)的时候，Boyer和Moore线性时间投票算法被建议了。

如果您按照链接到该站点，将逐步解释该算法是如何工作的。对于给定的序列，AAACCBBCCCBCC给出了正确的解决方案。

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

• 如果计数器为0，则将当前候选对象设置为e，并将计数器设置为1。
• 如果计数器不是0，则根据e是否是当前候选值来增加或减少计数器。

当我们完成时，目前的候选人是多数，如果有多数。

如果我把这个算法用在一张纸上，用AAACCBB作为输入，那么推荐的候选人就会变成B，这显然是错误的。

在我看来，有两种可能性

1. 除了AAACCBBCCCBCC，作者从来没有尝试过他们的算法，它们完全没有能力，应该被当场发射(怀疑是完全错误的)。
2. --我显然遗漏了一些东西--，必须从堆栈溢出中被禁止，永远不要再被允许触及任何涉及逻辑的东西。

注意:这是一个来自Niek Sanders的算法的C++实现。我相信他正确地实现了这个想法，因此它也有同样的问题(或者不是吗？)

Answer 1

该算法只有在集合占多数时才能工作--超过一半的元素是相同的。在您的示例中，AAACCBB没有这样的多数。最常见的字母发生3次，字符串长度为7。

Answer 2

这是对其他解释的一个小但重要的补充。摩尔投票算法分为两部分-

1. 运行摩尔投票算法的第一部分，只为多数元素提供一个候选。注意这里的“候选人”这个词。
2. 在第二部分中，我们需要再次对数组进行迭代，以确定该候选对象是否出现最大次数(即大于大小/2次)。

第一次迭代是查找候选项，第二次迭代是检查该元素在给定数组中是否发生了大部分时间。

所以时间复杂度是：O(n) + O(n) ≈ O(n)

Answer 3

从第一个相互关联的问题：

具有数组中半数以上的条目等于N的属性

来自Boyer和Moore的页面：

序列中的哪一个元素占大多数，只要有这样的元素。

这两种算法都明确地假设一个元素发生至少N/2次。(请特别注意，“多数”与“最常见”并不相同。)