线性时间多数元素算法？

Question

线性时间多数元素算法？

algorithmlanguage-agnosticcomplexity-theory

13

有没有人能够想出一种在线性时间内确定列表中多数元素的算法？该算法应使用 O(1) 空间。

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

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

[Output] 1

[编辑说明]这个问题存在技术错误。为了不破坏已接受答案的措辞，我选择保留它，并请查看已接受答案，该答案纠正了错误并解释了原因。

- Anil Katti

7个回答

9

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

你扫描一个列表（或流）并维护一个计数器。最初counter = 0，majority_element = null。当你扫描时，如果计数器为0，则将当前元素视为主要元素并增加计数器。如果counter != 0，则根据当前元素是否为当前多数元素增加或减少计数器。

如果没有多数，这种算法无法给出多数。如果您想了解正确性级别，则还需要进行一次验证，以确保它实际上是多数（即，>= 50％）。

- user308808

2

如果您能稍微描述一下，那将是一个很好的答案。 - Matthieu M.

1

它很简单。你扫描一个列表（或流）并维护一个计数器。最初计数器= 0，majority_element = null。扫描时，如果计数器为0，则假定当前元素为主要元素并增加计数器。如果计数器！= 0，则根据当前元素是否为当前大多数元素递增或递减计数器。如果没有主要元素，则此算法不会给出主要元素。如果您想要正确性的水平，则需要进行一次额外的遍历以验证它是否实际上是大多数（即> = 50％）。 - user308808

7

这是一个常见的挑战问题，答案是不可能的。具有主要元素的字符串语言不是正则的（这可以通过泵引理轻松证明），因此没有办法在恒定空间中识别它。

当然，诀窍在于您需要一个计数器变量，它需要O(log n)的空间，但由于n被限制为2^32或2^64，并且您的计算机实际上是一个有着~8^(ramsize+hddsize)状态的有限状态机，所有操作都是O(1)的。

- R.. GitHub STOP HELPING ICE

我有这样的印象，你正在尝试解决一个更加复杂的问题，而我认为我也已经解决了OP的问题... 你介意审查一下我的答案吗？ - Matthieu M.

定理：一个语言是正则的，当且仅当它可以在O(1)空间中被识别。我将对“识别具有大多数元素的数组”和“查找大多数元素（如果存在）”的等价性进行一些手波。现在，泵引理是证明一个语言不是正则的标准工具，而且非常容易使用。通过它，您可以证明由具有大多数元素的数组组成的语言不是正则的。（作为练习，请尝试找到一个正则表达式，匹配具有大多数元素的这样的字符串，其中成员可以是ASCII字母。你做不到。） - R.. GitHub STOP HELPING ICE

[@R..] 我对计算理论非常感兴趣，并担任过两次教学助理。我有一个问题：我相信将任何上下文无关文法转换为工作解析器的预测分析算法在时间上是线性的，不需要使用额外的空间。为什么它是“当且仅当”的？因为这意味着任何在O(1)空间中被识别的语言都是正则的！还要考虑(a^n)(b^n)(c^n)语言（既不是正则的也不是上下文无关的），但却有一个O(1)空间的解决方案！请告诉我我错过了什么... - OmarOthman

1

它没有O(1)的空间解决方案。计数到n需要O(log n)或至少O(log log n)的空间。 - R.. GitHub STOP HELPING ICE

7

我认为使用Boyer-Moore算法是可能的，但不是直接的。

正如Matthew所述，Boyer-Moore只能保证在稍微不同的多数定义下找到多数元素，称为严格多数。您的定义略微弱一些，但差别不大。

以下是具体步骤：

1. 执行Boyer-Moore算法：O(N)时间，O(1)空间 2. 检查候选项是否符合条件：O(N)时间，O(1)空间 3. 如果不符合条件，则执行Boyer-Moore算法，但忽略“失败”的候选项实例：O(N)时间，O(1)空间 4. 检查（新的）候选项是否符合条件：O(N)时间，O(1)空间

第1和第2步很简单。第3步之所以有效，是因为通过删除失败的候选项实例，我们现在正在寻找严格多数元素。第4步是可选的，只有在存在没有多数元素的可能性时才使用。

- Matthieu M.

1

这是标准的“答案”，解决了提问者想要问的问题，但 O(1) 实际上是错误的。存储是一个或多个整数变量，其值可以达到 n，因此需要 log n 的空间。然而，对于实际目的，log n 通常被限制在像 32 或 64 这样的常数范围内。 :-) - R.. GitHub STOP HELPING ICE

啊，我明白你的意思了。确实计数器的大小取决于N :) - Matthieu M.

是的，我认为这个问题中“majority”的定义是正确的。很好，点赞。 - Matthew Slattery

2

如果你知道大多数元素在数组大小的一半以上，那么就有这样的算法。您需要跟踪最常见的元素及其重复次数。当您开始时，该元素是第一个，并且有一个重复。如果下一个元素与当前最常见元素不同，则从重复中减去一。如果重复次数变为零，则将最常见元素更改为您当前正在观察的元素，并将重复次数设置为1。

- Mariy

0

使用堆排序的预阶段：

为数组元素构建一个堆，其运行时间为线性时间 -> O(n)。
然后取（N/2）个元素并搜索它的上层父节点是否全部相等 -> O(n/2)

如果全部相等，则（N/2）个元素是答案。

因此，总体时间复杂度为O(n) + O(n/2) -> O(n)。

- pankiii

0

我可能错了，但是在O(n)的执行时间和常量内存使用的组合似乎对我来说是不可能的。不使用额外的空间需要进行排序。最快的比较排序是O(n log n)。

使用基数排序，您可以获得更好的最坏情况执行时间，但会增加更多的内存使用。

- Thorarin

为什么“需要排序”？确实有这样的算法（请注意问题：它只是想要一些元素，该元素至少出现n/2次，如果存在这样的元素（这相当特殊！））。 - ShreevatsaR

@ShreevatsaR：你能告诉我这个算法叫什么吗？因为我怀疑它不是O(n)。 - Thorarin

@Thorarin：这是一个非常好的算法，由于Boyer-Moore算法，可以看看numes的回答。基本上，你只需要保持一个字符的计数，每当你看到另一个字符时就将其减少，并在计数变为0时更新该字符。(顺便说一下，我不是那个对这个答案进行了负评的人。) - ShreevatsaR

@Thorarin：不能想出一个算法并不意味着它不存在。证明下限是很困难的 :) - Matthieu M.

你的答案是正确的；谁给你点了踩都是白痴。使用泵引理很容易证明没有 O(1) 的空间解决方案。 - R.. GitHub STOP HELPING ICE

显示剩余2条评论

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Matthew Slattery · Accepted Answer

我猜Boyer-Moore算法（由nunes链接并由其他回答中的cldy描述）是问题的预期答案；但是，问题中“多数元素”的定义太弱了，无法保证算法有效。

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

如果存在严格多数元素，则Boyer-Moore算法会找到一个具有严格多数的元素。（如果您事先不知道是否确实有这样的元素，则必须对列表进行第二次遍历以检查结果。）

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

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

示例输入：1、2、1、1、3、2

输出：1

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

它碰巧在这个特定情况下起作用：

 输入：1、2、1、1、3、2
 读取1：计数==0，因此将候选项设置为1，并将计数设置为1
 读取2：计数！=0，元素！=候选人（1），因此将计数减少到0
 读取1：计数==0，因此将候选项设置为1，并将计数设置为1
 读取1：计数！=0，元素==候选人（1），因此将计数增加到2
 读取3：计数！=0，元素！=候选人（1），因此将计数减少到1
 读取2：计数！=0，元素！=候选人（1），因此将计数减少到0
 结果是当前候选人：1

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

输入：1, 2, 1, 2, 3, 1
读取1：count == 0，因此将候选项设置为1，并将计数设置为1
读取2：count != 0，element != candidate（1），因此将计数减少为0
读取1：count == 0，因此将候选项设置为1，并将计数设置为1
读取2：count != 0，element != candidate（1），因此将计数减少为0
读取3：count == 0，因此将候选项设置为3，并将计数设置为1
读取1：count != 0，element != candidate（3），因此将计数减少为0
结果是当前候选项：3