查找是否有在出现的阵列的数目超过N/8倍

Question

的问题是：

描述了一种算法，在O（n）的发现的时间，如果存在n个数字，一个阵列出现超过n/8次的数字。

现在我有这就是答案：

我们会做的选择在地方的数字：N/9,2 * N/9,3 * N/9，...，8 * N/9，并且检查这8位候选人中是否有一位出现至少n/8次。

但我不明白为什么会这个算法的工作。

例如，考虑以下数组： [3,3,1,3,2,3,4,3,5,3,6,3,7,3,8,3,9,3] 。

因此，这里n = 18，如果这个算法的候选人将是1,2,4,5,6,7,8,9，当我们检查这些数字是否至少出现n/8次答案将是否定的，但实际上3答案是肯定的。

所以我不明白这是为什么算法正确...

Answer 1

这里的关键结论是选择，资本尤其是当有特殊的意义：它引用找到的第k在最大的入境问题一个未排序的数组。也许有点令人惊讶的先验，这可以在线性时间内完成，例如使用5中位数枢轴策略与QuickSelect算法相结合。所以如果你用大写字母S选择n/9，2n/9，...条目（成本：9 *线性 - 这是线性的），你一定会找到任何出现n/8次的条目。然后再次遍历数组以计算每个候选项的出现次数，然后重新开始。