多数投票算法-错吗？

Question

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

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 )进行了尝试。这实际上也适用于上面引用的算法(该算法返回"No多数元素！“)。问题是:每当多数元素和其他元素之间发生交替时，数组中的最后一个不是多数元素的元素就会被选中。如果有的话，请纠正我的错误想法，并告诉我如何在实现中避免它。

Answer 1

算法是正确的:在你的例子中没有多数元素。只有当元素的大于值的50%时，元素才占多数。

如果您希望检测最频繁的元素有一个计数N/2的情况，那么我看不出有任何方法可以在一次传递和O(1)空间内完成。我最好的尝试是：

• 运行相同的算法，但也要记住前一个候选人。
• 如果在最后一个元素切换，那么正确的答案要么是当前的，要么是以前的候选人。
• 运行另一个pass，计算每一个的数目，并对它们进行比较。

Answer 2

好的，我想我现在明白了@sverre的意思。这是一个证明它有效的证据：

• 如果N/2元素恰好是相同的值(调用此值m)，则N必须是偶数。
• 将这些元素分为两部分:第一个N-1元素和最后一个元素。假定所有的N/2元素都等于m，那么两者都是：

1. the last element is not `m`, in which case `N/2` of the first `N-1` elements are equal to `m`, and therefore the first `N-1` elements have a strict majority `m`; or
2. the last element is `m`, in which case `(N/2)-1` of the first `N-1` elements are equal to `m`, and therefore the first `N-1` elements do not have a strict majority. 

​

• (在案例1中)，m是处理最后一个元素之前的候选元素(因为在那时，我们刚刚处理了N-1元素，并且我们知道在这种情况下确实存在严格的多数，因此候选人必须是正确的答案)。在案例2中，
• )，m是最后一个元素本身。(这就是让我困惑的地方:在算法的通常实现中，这不一定会在处理过程中成为候选。)

。

所以：

candidate.

• For
• 对于严格多数(> N/2元素相同)，答案(如果存在的话)是最终的>= N/2非严格多数(>= N/2元素相同)，答案(如果存在)是：

之一。

1. the final candidate; or
2. the candidate just before processing the last element; or
3. the last element.

​