查找在线性时间内出现超过n/4次的所有元素

Question

此问题是Skiena的4-11。找到多数元素的解决方案 - 重复超过半数是多数算法。我们可以用它来找出所有重复n/4次的数字吗？

Answer 1

正如你没有提及空间复杂性，一个可能的解决方案是使用hashtable作为映射到计数的元素，然后你可以增加计数，如果找到元素。

Answer 2

请参阅http://www.cs.yale.edu/homes/el327/datamining2011aFiles/ASimpleAlgorithmForFindingFrequentElementsInStreamsAndBags.pdf了解使用常量内存并在线性时间内运行的解决方案，该解决方案将为发生超过n/4次的元素找到3个候选项。请注意，如果您假设您的数据是以只能通过一次的流的形式提供的，那么这是您可以做的最好的 - 您必须再次通过该流以测试3个候选人中的每一个以查看是否它在流中出现超过n/4次。然而，如果你先假设有3个元素发生的次数超过n/4次，那么你只需要经过一次流，这样你就可以得到一个线性时间在线算法（只经过一次流），只需要一个常量存储。

Answer 3

查找，通过摩尔定律表决权算法

给定的链接，Moore的投票算法中（http://www.geeksforgeeks.org/majority-element/）的方法见3出现n/2 times大部分元素。

时间：O（n）的

现在发现多数元素之后，再次remove the majority element扫描阵列或使其-1.

时间：O（n）的

现在申请摩尔投票算法对阵列的其余元素（但现在忽略-1，因为它已经包含在前面）。广大新元素出现n/4 times.

时间：O（n）的

总时间：O（n）的

额外的空间：O（1）

你可以为出现超过n/8，n/16，...的元素做它时间

编辑：

有当在阵列中没有多数元件可能存在的情况下：

对于例如如果输入数组是{3, 1, 2, 2, 1, 2, 3, 3}那么输出应该是[2, 3]。

鉴于大小N和K个数组，发现看起来比N/K以上所有元素次

请参阅此链接的答案： https://stackoverflow.com/a/24642388/3714537

参考文献：

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

Answer 4

Misra and Gries描述了几种方法。我不完全了解他们的论文，但一个关键的想法是使用一袋。

Boyer and Moore's original majority algorithm paper有很多难以理解的样张和Fortran代码正式verificatiom的讨论，但它的大部分算法如何工作的解释非常好的开始。关键概念始于如果大多数元素是A，并且您一次删除一个A副本和其他副本，那么最终您将只拥有A的副本。接下来，应该清楚的是，移除两个不同的项目，两个都不是A，只能增加A所持有的多数。因此，只要它们不同，删除任意项都是安全的。这个想法可以被具体化。将第一个项目从列表中取出并粘贴在一个盒子中。把下一件物品拿出来放在箱子里。如果他们一样，让他们都坐在那里。如果新的是不同的，请将其与盒子中的物品一起扔掉。重复，直到所有项目都在箱子或垃圾箱中。由于箱子一次只允许有一种物品，因此它可以非常有效地表示为(item type, count)。

查找所有可能出现的时间超过n/k次的项目的概括很简单，但解释它的工作原理有点困难。基本的想法是，我们可以找到并摧毁k不同的元素组而不改变任何东西。为什么？如果w > n/k然后w-1 > (n-k)/k。也就是说，如果我们拿走其中一个流行元素，而且我们还带走k-1其他元素，那么流行元素仍然很受欢迎！

执行：取代只允许一个种类的项目在框中，允许k-1其中。每当你看到一组k不同的项目出现（也就是说，有k-1类型在框中，并且到达的不匹配任何一个），你扔垃圾中的每种类型之一，包括一个刚刚到达。我们应该为这个“盒子”使用什么数据结构？好吧，当然是一个包！正如Misra和Gries所解释的那样，如果元素可以被排序，那么一个具有O（log k）基本操作的基于树的包就会给整个算法的复杂度为O（n log k）。需要注意的一点是，删除每个元素之一的操作是昂贵的（我认为O（k log k）），但是这些成本是在这些元素的到达之间分摊的，所以没什么大不了的。当然，如果你的元素是可散列的而不是可订购的，你可以使用基于散列的包，而在某些常见的假设下，它可以提供更好的渐近性能（但不能保证）。如果你的元素是从一个有限的小集合中抽取的，你可以保证这一点。如果他们只能比较等于，那么你的包变得更加昂贵，我敢肯定，你最终会得到类似O（nk）的东西。