多数投票算法 - 错误？

Question

如果存在这样的元素,则多数表决算法决定序列中的哪个元素占多数.这是我在试图理解它时发现的最常被引用的链接.

http://www.cs.utexas.edu/~moore/best-ideas/mjrty/index.html

此外,我们在这里有一个讨论问题的链接:

如何找到重复至少N/2次的数组元素？

问题是标记为正确的答案是错误的.请注意,该问题实际上允许输入具有单个元素的正好 N/2个副本(不一定多于 N/2,如通常在多数元素检测算法中假设的那样).

我复制了代码并尝试使用[1,2,3,2]和[1,2,3,2,6,2]等输入(产生3和6的结果).这实际上也适用于上面引用的算法(返回"无多数元素!").问题在于:只要多数元素和其他任何元素之间存在交替,就会选择数组中不是多数元素的最后一个元素.请更正我的错误想法,并告诉我如何在实施中避免它.

Answer 1

算法是正确的:您的示例中没有多数元素.仅当元素超过值的50%时,元素才占多数.

如果你想检测最频繁的元素有一个计数的情况N/2,那么我没有看到任何方法在一个通道和O(1)空间中这样做.我最好的尝试是:

• 运行与以前相同的算法,但也记住前一个候选人.
• 如果您切换到最后一个元素,那么正确的答案是您当前或之前的候选人.
• 运行另一个传递,计算每个传递的数量,并进行比较.