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

Question

我正在追求 Algorithms, Part I Coursera 上的类(class)，其中一个面试题(未评分)如下:

Decimal dominants. Given an array with n keys, design an algorithm to find all values that occur more than n/10 times. The expected running time of your algorithm should be linear.

它有一个提示:

determine the (n/10)th largest key using quickselect and check if it occurs more than n/10 times.

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

有一个 paper这为 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是问题定义中固定的一个数字，所以整个操作只算线性时间。