algorithm - 概率选择算法

Question

给出的是:

• 一个长度为 N 的数组。
• 数组包含整数。
• 整数不一定是有序的。

找到一个算法:

• 返回第 K 个最小数组元素(近似值)。
• 具有 O(N log N) 的运行时复杂度和 O(log N) 的空间复杂度。
• 算法不必是确定性的。在概率算法的情况下，还提供了对近似结果质量的度量。

Answer 1

将问题视为类似于快速排序的问题。给定数组中的一个元素，您可以在 O(n) 时间和 O(lg n) 空间内获得它的排名。您可以使用二进制搜索在 O(lg n) 次迭代中找到具有给定等级的元素，总共 O(lg n) 空间和 O(n lg n) 时间。