topK快速选择

https://zhuanlan.zhihu.com/p/76734219

最简单的，排序后找第K个

用快速排序： 所以结果是nlogn 快排的空间复杂度是 O(1)

只排序前K个

冒泡排序

O(n*k)

可以基于快速排序和二分来实现一个减治算法， 这里命名为快速选择算法。

时间复杂度跟快排一样： 一般是nlogn， 最坏是n^2 空间复杂度是logn，最坏到极端情况递归n次，O(n)

手撕：100万个数字里面找到最大的1000个数字怎么找

面试官追问

• 你刚才提到了用“最小堆”，那为什么不用“最大堆”呢？如果用最大堆来解决这个问题，思路是怎样的？它的时间和空间复杂度又如何？和最小堆相比，优劣在哪里？

• 这个方案一个很大的优点是空间复杂度只有 O(K)。这个优点在什么场景下会变得至关重要？如果这 100 万个数字因为太大，无法一次性加载到内存里，只能以数据流（Stream）的形式逐个读取，你的最小堆方案还能工作吗？

• 除了堆排序的思路，你还了解其他解决 Top K 问题的算法吗？比如，你知道快速排序的“划分”（Partition）思想如何被应用到这个问题上吗？（提示：Quickselect 算法）

• 如果 K 的值非常大，比如 K 接近 N/2（在 100 万里找最大的 50 万个），你觉得最小堆的方案还是最优的吗？为什么？ 现在我们把场景再复杂化一点：这 100 万个数字分布在 100 台机器上，每台机器上有 1 万个。你不能把所有数据都拉到一台机器上处理。你会如何设计一个分布式方案来解决这个问题？