c - 多数投票算法-错误？

多数投票算法决定序列中的哪个元素占多数，前提是存在这样的元素。这是我尝试了解它时最常引用的链接。

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

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

How to find the element of an array that is repeated at least N/2 times?

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

我复制了代码，并使用[1、2、3、2]和[1、2、3、2、6、2]之类的输入进行了尝试(产生3和6的结果)。这实际上也适用于上面引用的算法(该算法返回“No Majority Element!”)。问题是这样的:只要在多数元素和任何其他元素之间存在交替，就会选择数组中不是多数元素的最后一个元素。请纠正我的错误想法(如有)，并告诉我如何在实现中避免它。

最佳答案

该算法是正确的:您的示例中没有多数元素。仅当大于值的50％时，该元素才占多数。

如果您希望检测最频繁的元素计数为N/2的情况，那么我看不出有任何方法可以一次性通过O(1)空间。我最好的尝试是:

运行与以前相同的算法，但也要记住前一个候选者。

如果您切换到最后一个元素，那么正确的答案是您当前的候选人或您以前的候选人。

运行另一遍，计算每遍的数量，然后进行比较。