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

Question

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

Answer 1

米斯拉和格里斯描述了几种方法。我不完全理解他们的论文，但一个关键的想法是使用bag。

Boyer 和 Moore 最初的多数算法论文有很多难以理解的证明和对 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 k) 基本操作的基于树的包将使整个算法的复杂度为 O(n log k)。需要注意的一点是，删除每个元素之一的操作有点昂贵（典型实现的 O(k)），但该成本会根据这些元素的到达进行摊销，因此这没什么大不了的。当然，如果您的元素是可散列的而不是可排序的，则可以使用基于散列的包，在某些常见假设下，这将提供更好的渐近性能（但不能保证）。如果您的元素是从一个小的有限集合中提取的，您可以保证这一点。如果它们只能比较equal，那么你的包会变得更贵，我很确定你最终会得到类似 O(nk) 的东西。

Answer 2

由于您没有提到空间复杂度，一种可能的解决方案是对映射到 count 的元素使用哈希表，然后如果找到该元素，您只需增加 count 即可。