问题描述
谁能想到一个线性时间的算法来确定的元素列表中的大多数元素？该算法应使用 O（1）的空间。
Can anyone think of a linear time algorithm for determining a majority element in a list of elements? The algorithm should use O(1) space.
如果n是列表的大小，一个的多数元素的是发生至少 CEIL（N / 2）倍的元件。
If n is the size of the list, a majority element is an element that occurs at least ceil(n / 2) times.
[输入] 1，2，1，1，3，2
[Input] 1, 2, 1, 1, 3, 2
【输出】1
[编者注] 这个问题有一个技术性错误。 I $ pferred离开它，以免破坏公认的答案，这纠正了错误，并讨论为什么措辞p $。请接受的答案。的
This question has a technical mistake. I preferred to leave it so as not to spoil the wording of the accepted answer, which corrects the mistake and discusses why. Please check the accepted answer.
推荐答案
我猜想，该博耶 - 穆尔算法（如由努涅斯挂钩和cldy在其他的答案中描述）是预期问题的答案;但在问题的多数元素的定义是太弱，无法保证算法工作。
I would guess that the Boyer-Moore algorithm (as linked to by nunes and described by cldy in other answers) is the intended answer to the question; but the definition of "majority element" in the question is too weak to guarantee that the algorithm will work.
如果n是列表的大小。大多数元件是发生至少CEIL（N / 2）倍的元件。
该博耶 - 穆尔算法找到了的严格的大部分元素，如果的存在这样一个元素。 （如果你不事先知道你有这样的一个元素，您必须通过列表，进行第二次扫描检查的结果。）
The Boyer-Moore algorithm finds an element with a strict majority, if such an element exists. (If you don't know in advance that you do have such an element, you have to make a second pass through the list to check the result.)
有关严格的大多数，你需要......严格比地面以上（N / 2）次，而不是......至少CEIL（N / 2）次。
For a strict majority, you need "... strictly more than floor(n/2) times", not "... at least ceil(n/2) times".
在你的榜样，1出现3次，其他值出现3次：
In your example, "1" occurs 3 times, and other values occur 3 times:
实施例输入：1，2，1，1，3，2
输出：1
但你需要4个元素与严格的大部分相同的值。
but you need 4 elements with the same value for a strict majority.
它确实发生在这种特殊情况下的工作：
It does happen to work in this particular case:
Input: 1, 2, 1, 1, 3, 2
Read 1: count == 0, so set candidate to 1, and set count to 1
Read 2: count != 0, element != candidate (1), so decrement count to 0
Read 1: count == 0, so set candidate to 1, and set count to 1
Read 1: count != 0, element == candidate (1), so increment count to 2
Read 3: count != 0, element != candidate (1), so decrement count to 1
Read 2: count != 0, element != candidate (1), so decrement count to 0
Result is current candidate: 1
但看，如果最后的1和2的结尾被换了会发生什么：
but look what happens if the final "1" and the "2" at the end are swapped over:
Input: 1, 2, 1, 2, 3, 1
Read 1: count == 0, so set candidate to 1, and set count to 1
Read 2: count != 0, element != candidate (1), so decrement count to 0
Read 1: count == 0, so set candidate to 1, and set count to 1
Read 2: count != 0, element != candidate (1), so decrement count to 0
Read 3: count == 0, so set candidate to 3, and set count to 1
Read 1: count != 0, element != candidate (3), so decrement count to 0
Result is current candidate: 3
这篇关于线性时间多数算法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！