多数表决算法 – 错误？

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

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)空间中我看不到任何方法。 我最好的尝试是：

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

Answer 2

好的，所以我想我现在明白@sverre正在做什么。 这是一个certificate它有效：

• 如果恰好N/2元素是相同的值（调用此值m ），则N必须是偶数。

• 将这些元素拆分为两部分：第一个N-1元素和最后一个元素。 假设总共N/2元素等于m ，则：

  1. 最后一个元素不是m ，在这种情况下，第一个N-1元素的N/2等于m ，因此第一个N-1元素具有严格的多数m ; 要么
  2. 最后一个元素是m ，在这种情况下，前N-1元素的(N/2)-1等于m ，因此前N-1元素不具有严格的多数。

• 在情况1）中， m是处理最后一个元素之前的候选者（因为在那时，我们刚刚处理了N-1元素，并且我们知道在这种情况下确实存在严格多数，因此候选者必须是正确答案）。

• 在情况2）中， m是最后一个元素。 （这是令我困惑的部分：在算法的通常实现中，这不一定会成为候选者，因为它被处理。）

所以：

• 对于严格的大多数（ > N/2元素相同），答案（如果存在）是最终候选者。

• 对于非严格多数（ >= N/2元素相同），答案（如果存在）是以下之一：

  1. 最终候选人; 要么
  2. 在处理最后一个元素之前的候选者; 要么
  3. 最后一个元素。