概率选择算法

Question

鉴于:

• 一长串N.
• 该数组包含整数.
• 整数不一定是排序的.

找到一个算法:

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

Answer 1

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