algorithm - 线性时间多数算法？

Question

谁能想出一个线性时间算法来确定元素列表中的多数元素？该算法应使用 O(1) 空间。

如果 n 是列表的大小，多数元素 是至少出现 ceil(n/2) 次的元素。

[Input] 1, 2, 1, 1, 3, 2

[Output] 1

[编者注]这题有技术错误。我宁愿留下它，以免破坏已接受答案的措辞，它纠正了错误并讨论了原因。请检查已接受的答案。

Answer 1

我猜 Boyer-Moore 算法(由 nunes 链接并在其他答案中由 cldy 描述)是该问题的预期答案；但是问题中“多数元素”的定义太弱，无法保证算法会起作用。

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

Boyer-Moore 算法找到具有严格多数的元素，如果这样的元素存在。 (如果你事先不知道你确实有这样一个元素，你必须第二次遍历列表以检查结果。)

对于严格多数，您需要“...严格超过 floor(n/2) 次”，而不是“...至少 ceil(n/2) 次”。

在您的示例中，“1”出现了 3 次，其他值出现了 3 次:

Example input: 1, 2, 1, 1, 3, 2

Output: 1

但是您需要 4 个具有相同值的元素才能达到严格多数。

它确实适用于这种特殊情况:

Input: 1, 2, 1, 1, 3, 2Read 1: count == 0, so set candidate to 1, and set count to 1Read 2: count != 0, element != candidate (1), so decrement count to 0Read 1: count == 0, so set candidate to 1, and set count to 1Read 1: count != 0, element == candidate (1), so increment count to 2Read 3: count != 0, element != candidate (1), so decrement count to 1Read 2: count != 0, element != candidate (1), so decrement count to 0Result is current candidate: 1

但如果最后的“1”和末尾的“2”互换，看看会发生什么:

Input: 1, 2, 1, 2, 3, 1Read 1: count == 0, so set candidate to 1, and set count to 1Read 2: count != 0, element != candidate (1), so decrement count to 0Read 1: count == 0, so set candidate to 1, and set count to 1Read 2: count != 0, element != candidate (1), so decrement count to 0Read 3: count == 0, so set candidate to 3, and set count to 1Read 1: count != 0, element != candidate (3), so decrement count to 0Result is current candidate: 3