线性时间多数算法？ [英] Linear time majority algorithm?

问题描述

谁能想到一个线性时间的算法来确定的元素列表中的大多数元素？该算法应使用 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）倍的元件。

If n is the size of the list. A majority element is an element that occurs at least ceil(n/2) times.

该博耶 - 穆尔算法找到了的严格的大部分元素，如果的存在这样一个元素。 （如果你不事先知道你有这样的一个元素，您必须通过列表，进行第二次扫描检查的结果。）

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

Example input: 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

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