topk 问题

排序后取前 K 个

算法复杂度 O(nlogn)

遍历 K 遍

算法复杂度 O(kn)

k 跟元素的小/大根堆

算法复杂度 O(nlogk)

快排序思想

1 选取一个数组 index,把比他小的放到左边,比他大的放到右边
2 如果 index >k,那么前 k 个在左边
如果 index=k,那么左边就是前 k 个
如果 index < k,那么前 k 个还需要加上右边的 k-index 个

平均算法复杂度 O(n),最坏 O(n2)

中位数的中位数

选取 pivot
1 数组分为 n/5 组,每组 5 个元素(多余的忽略)
2 这 n/5 个分组分别查找各自的中位数
3 对这些中位数再取他们的中位数
对这个 pivot 进行上面的快排思想