第 topK 问题

问题描述：在（无序）数组中找到第 $k$ 大 / 小的元素。

常用的解法有：

完全排序（快排）

思想：排序后直接定位第 $k$ 个。
时间：平均 $O (Nl g N)$ ，最坏 $O (N^{2})$ ，
空间：平均 $O (l g N)$ ，最坏 $O (N)$ 。
STL：std::sort。实现：内省排序 + 插入排序。
TIP：当数据满足某些排序算法的特殊要求时（例如计数、基数等），可以手动实现排序。

部分排序

思想：排序后直接定位第 $k$ 个。
时间：最坏 $O (Nl g k)$ 。
空间：最坏 $O (1)$ 。
STL：std::partial_sort。内部为 std::make_heap + std::sort_heap。实现： $Fl oy d$ 原地建堆 $O (k)$ ，动态维护堆有序 $O ((N - k) l g k)$ ，最后堆排序 $O (k l g k)$ 。

快速选择

思想：排定第 $k$ 个即结束。
时间：平均 $O (N)$ ，最坏 $O (N^{2})$ 。
空间：平均 $O (l g N)$ ，最坏 $O (N)$ 。
STL：std::nth_element。实现：循环式减治，med_of_3选基准，双向快排式切分，区间长度低于阈值时转向插入排序。STL 还提供了 std::partition 函数以供使用。
平均时间复杂度的非严谨证明（正确性未知）：
算法为减治思想，每次切分耗时 $O (N)$ ，显然根据主定理有：
$T (N) = T (\frac{N}{2}) + O (N) ⟹ T (N) = O (N)$
Q.E.D.

BFPRT（median of medians）

BFPRT = 基本的快速选择 + median_of_medians法选基准，取样大小为 $5$ 。
思想：排定第 $k$ 个即结束。
时间：平均 $O (N)$ ，最坏 $O (N)$ 。
空间：平均 $O (l g N)$ ，最坏 $O (l g N)$ 。
STL：除使用 median_of_medians法选基准外，基本与std::nth_element实现一致。
最坏时间复杂度的证明：

图片来源：https://leetcode.cn/problems/kth-largest-element-in-an-array/solution/javascriptsi-chong-fang-shi-jie-topkwen-ti-by-user/
注：该作者似乎是搬运，原文章地址为：https://zhuanlan.zhihu.com/p/31498036

参考：https://en.wikipedia.org/wiki/Median_of_medians

优先队列（完全入堆）

思想：全部入堆，最后弹出顶部 $k$ 个。
时间：最坏 $O (Nl g N)$ 。
空间：最坏 $O (N)$ 。
STL：std::priority_queue。内部实现：std::make_heap，std::push_heap，std::pop_heap。参考：https://www.cplusplus.com/reference/queue/priority_queue/

优先队列（部分入堆）

思想：动态维护大小为 $k$ 的堆。
时间：最坏入堆 $O (k l g k)$ ，维护 $O ((N - k) l g k)$ 。
空间：最坏 $O (k)$ 。
STL：同上。

二叉搜索树（BST，或称二叉排序树）

与优先队列使用方法类似，因为优先队列的实现即为二叉堆。
参考： https://leetcode.cn/problems/zui-xiao-de-kge-shu-lcof/solution/3chong-jie-fa-miao-sha-topkkuai-pai-dui-er-cha-sou/

前 topK 问题

解决思路与 “第 topK 问题” 类似。
通用的解法是：将前 topK 问题转换为第 topK 问题，例如使用快速选择或BFPRT求第 topK 个数，再遍历一遍原数组，收集比该数小/大的所有数即可。