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

Question

当我阅读这篇文章(Find the most common entry in an array)时，Boyer and Moore's Linear Time Voting Algorithm有人建议。

如果您点击该站点的链接，将逐步解释该算法的工作原理。对于给定的序列，AAACCBBCCCBCC 它给出了正确的解决方案。

When we move the pointer forward over an element e:

• If the counter is 0, we set the current candidate to e and we set the counter to 1.
• If the counter is not 0, we increment or decrement the counter according to whether e is the current candidate.

When we are done, the current candidate is the majority element, if there is a majority.

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

在我看来，有两种可能

1. 作者从未在 AAACCBBCCCBCC 以外的任何地方尝试过他们的算法，完全无能，应该当场解雇(怀疑)。
2. 我显然遗漏了一些东西，必须被禁止使用 Stackoverflow，并且再也不允许接触任何涉及逻辑的东西。

注意:这是一个C++ implementation of the algorithm来自尼克·桑德斯。我相信他正确地实现了这个想法，因此它有同样的问题(或者没有？)。

Answer 1

该算法仅在集合占多数时才有效——超过一半的元素相同。 AAACCBB 在你的例子中没有这样的多数。出现次数最多的字母出现3次，字符串长度为7。