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

Question

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

Answer 1

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

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

查找可能出现超过 n/k 次的所有项目的概括很简单，但解释它为什么起作用有点困难。基本思想是我们可以在不改变任何东西的情况下找到并销毁 k distinct 元素组。为什么？如果 w > n/k 则 w-1 > (n-k)/k。也就是说，如果我们拿走其中一个流行元素，同时我们也拿走 k-1 other 个元素，那么流行元素仍然流行!

实现:盒子中不再只允许 一种 种元素，而是允许 k-1 种元素。每当您看到一组 k 不同的 项目出现时(即，盒子中有 k-1 类型，并且到达的那个与其中任何一个都不匹配)，您将每种类型的一个扔进垃圾桶，包括刚到达的那个。我们应该为这个“盒子”使用什么数据结构？好吧，当然是一个包!正如 Misra 和 Gries 解释的那样，如果可以对元素进行排序，则具有 O(log k) 基本操作的基于树的包将为整个算法提供 O(n log k) 的复杂性。需要注意的一点是，删除每个元素中的一个的操作有点昂贵(对于典型的实现为 O(k))，但该成本会在这些元素到达时分摊，因此没什么大不了的。当然，如果您的元素是可散列的而不是可排序的，则可以改用基于散列的包，在某些常见假设下，这将提供更好的渐近性能(但不能保证)。如果你的元素是从一个小的有限集中抽取的，你可以保证这一点。如果只能比较它们的相等性，那么您的包会变得更贵，我敢肯定您最终会得到类似 O(nk) 的东西。