如何查找数组中出现次数超过 n/k 次的所有值？

Question

我正在Coursera 上学习算法，第一部分课程，其中一个面试问题（未评分）如下：

十进制占优。给定一个包含 n 个键的数组，设计一个算法来查找出现次数超过 n/10 次的所有值。算法的预期运行时间应该是线性的。

它有一个提示：

使用 quickselect 确定第 (n/10) 个最大的键并检查它是否出现超过 n/10 次。

我不明白 n/10 最大的键与 n/10 重复值有什么关系。它不会告诉我哪些值出现次数超过 n/10 次。

有一篇论文为 n/k 找到了更通用的解决方案，但我很难理解论文中的代码。

解决这个问题的一种方法是对输入数组进行排序，然后再计算每个不同值的出现次数。这将花费 O(nlogn) + O(n) 时间，这比问题要求的要多。

想法？

Answer 1

使用 QuickSelect 查找第 n/10 大键（即，如果数组已排序，将位于位置 n/10 的键）需要线性时间。如果此键的副本少于 n/10 个副本，那么您知道在排序顺序中它上面的任何内容都没有 n/10 个副本，因为在排序的键上方没有任何内容的 n/10 个副本的空间命令。如果有 n/10 或更多的副本，那么你已经发现了出现超过 n/10 次的东西，并且再一次不可能有比它更大的出现超过 n/10 次的东西，因为没有空间为了它。

现在您有一个最多 9n/10 个值的数组，该数组比您刚刚从 QuickSelect 中找到的键小。使用另一遍 QuickSelect 从这个左边数组的顶部找到键 n/10。和以前一样，您可能会找到出现 n/10 次或更多次的键，无论您是否这样做，您都会从数组中消除至少 n/10 个条目。

因此，您可以通过 10 次 QuickSelect 调用搜索整个数组，每次调用都需要线性时间。10 是问题定义中固定的数字，因此整个操作仅计为线性时间。

Answer 2

你是对的。

小数主导是 QuickSelect 之后的下一个候选：n/10、2*n/10..9*n/10，因此仅检查 n/10 索引是不够的

请注意，主导占据排序数组中的长期运行，并且当然至少具有上述索引的元素之一属于该运行。

例如，k = 3，N = 11。让元素 b 至少占据数组的 1/3。在这种情况下，排序数组可能看起来像

b b b b * * * * * * * 
* b b b b * * * * * * 
* * b b b b * * * * *     
* * * b b b b * * * *     
* * * * b b b b * * *
* * * * * b b b b * *
* * * * * b b b b * *
* * * * * * b b b b *
* * * * * * * b b b b
      ^       ^       //positions for quickselect

请注意，在任何情况下，主导元素（如果 k 主导确实存在）至少占据一个标记位置。因此，经过两轮快速选择，我们有两个候选人