假设我们有一个数组，我们希望找到它的 K 个最小值：
有两种方法：
1.使用快速选择算法（O(n)时间复杂度和O(1)空间）
2.使用最小堆数据结构（O(NlogK)时间复杂度和O(K)空间）
我想知道什么时候一个比另一个更受青睐。
我想这两个都可以分发。
检查这个out http://blog.teamleadnet.com/2012/07/quick-select-algorithm-find-kth-element.html:-
比排序或堆更快的选择
由于对整个数据集进行排序非常慢，因此选择
前 K 个项目，并仅对少数“顶部”元素进行排序，给出
当整个数据集在她页面排序时给用户留下的印象
通过结果集。这将给出 O(k*log(k) +
n) 与 O(n*log(n)) 相反，如果 K 合理，则速度要快得多
小（例如几百）。
另一种方法是使用堆并不断弹出
最小的数字，同时放回较大的数字，因为我们收到了 N
数字作为流。这适用于 O(n*log(K)) 运行时间，如下所示
堆包含 K 个元素，因此当我们测试 N 时，高度为 log(K)
总数，尽管预计运行时间大于
快速选择和排序组合。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
