多数表决算法 - 错了吗？ [英] Majority Voting Algorithm - WRONG?

问题描述

一个多数投票算法决定哪一个序列的元素居多，只要有这样的元素。下面是我发现当我试图去了解它最常被引用链接。

A majority voting algorithm decides which element of a sequence is in the majority, provided there is such an element. Here is the most frequently-cited link that I found when I was trying to understand it.

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

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

Besides, we have here a link that discusses the problem:

<一个href="http://stackoverflow.com/questions/3740371/finding-the-max-repeated-element-in-an-array">Finding最大反复数组中的元素

现在的问题是，答案标记为正确是错误的。注意，问题实际上允许输入具有的恰好的N / 2个拷贝的单个元件（不一定的大于的N / 2个如通常假定在大多数元件检测算法）

The problem is that the answer marked as correct is WRONG. Note that the question actually allows the input to have exactly N / 2 copies of a single element (not necessarily more than N / 2 as usually assumed in majority element detection algorithms).

我复制了code，并试图用类似的输入[1，2，3，2]和[1，2，3，2，6，2]（产生的结果3和6）。这实际上也适用于上面提到的算法（返回否多数元！）。问题是这样的：只要有大部分元件和别的之间的交替，在数组中的最后一个元素，这不是大多数元素被选中。请纠正我的错误思想，如果有的话，告诉我如何避免在执行。

I copied the code and tried it with inputs like [1, 2, 3, 2] and [1, 2, 3, 2, 6, 2] (producing results of 3 and 6). This actually applies as well to the algorithm cited above (which returns "No Majority Element!"). The problem is this: Whenever there's an alternation between the majority element and anything else, the last element in the array that's not the majority element is chosen. Please correct my wrong thoughts if any, and tell me about how to avoid it in the implementation.

推荐答案

该算法是正确的：有一个在您的例子无多数元素。一个元素居多，只有当它是超过值的50％。

The algorithm is correct: there is no majority element in your examples. An element is in the majority only if it is more than 50% of the values.

如果您希望检测，其中最常见的元素的计数的情况下 N / 2 ，那么我看不出有什么办法做到这一点在一个通和 O（1）的空间。我最好的尝试是：

If you wish to detect the case where the most frequent element has a count of N/2, then I don't see any way to do it in one pass and O(1) space. My best attempt is:

• 运行相同的算法和以前一样，但请记住previous候选人为好。
• 如果您在切换的最后一个元素，那么正确答案要么是你目前或previous候选人。
• 运行另一张通行证，每个计数的数量，并进行比较。

这篇关于多数表决算法 - 错了吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！