问查找在线性时间内出现n/4次以上的所有元素

EN

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

Boyer and Moore's original majority algorithm paper有许多难以理解的证明和关于FORTRAN代码的形式验证的讨论，但它有一个很好的开端来解释大多数算法是如何工作的。关键的概念始于这样的想法:如果大多数元素都是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 )个基本操作的树型包将使整个算法的复杂度为O(n log )。需要注意的一点是，删除每个元素中的一个元素的操作代价很高(我认为是O(k log k))，但该成本会在这些元素到达时摊销，所以这没什么大不了的。当然，如果您的元素是hashable而不是可排序的，您可以使用基于散列的包，在某些常见的假设下，这将提供更好的渐近性能(但不能保证)。如果你的元素是从一个很小的有限集中提取的，你可以保证这一点。如果它们只能进行相等的比较，那么你的包就会变得更贵，我敢肯定你最终会得到O(nk)这样的东西。

有关使用常量内存并在线性时间内运行的解决方案，请参阅this paper，它将为出现超过n/4次的元素找到3个候选元素。请注意，如果您假设您的数据是以流的形式给出的，并且只能通过一次，那么这就是您所能做的最好的事情--您必须再次通过流来测试3个候选对象中的每一个，以查看它在流中是否超过n/4次。然而，如果你假设有3个元素出现超过n/4次，那么你只需要遍历一次流，这样你就得到了一个线性时间在线算法(只遍历一次流)，它只需要常量存储。

通过Moore- n/2 times算法找出出现投票的大多数元素

有关摩尔的投票算法(http://www.geeksforgeeks.org/majority-element/)，请参阅给定链接的方法3。

时间:O(N)

现在，在找到多数元素后，再次扫描数组并将其设为remove the majority element或-1.

时间:O(N)

现在，在数组的其余元素上应用Moore Voting算法(但现在忽略-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/