求最小的 k 个元素:
一、 所谓的快排实际上是
QuickSelect(k),通过分治的方式找到第 k 个数, 总时间复杂度 是 O(N) 的,因为前 K 个数不要求有序。 这个方法的主要优点是平均时间复杂度最小 ,如果用
BFPRT 算法,可以把最坏时间复杂度降到 O(N)。
二、 堆排序有两种:
- 建立大小为 N 的小根堆,出堆 K 次得到最小的 K 个数。 建堆是 O(N),出堆一次
O(logN), 总时间复杂度 O(N+KlogN);
- 建立大小为 K 的大根堆,如果下一个数比堆顶大就替换掉堆顶元素并维护堆性质,每次操作都是 O(logK),总时间复杂度
O(NlogK)。这个方法的主要优点是空间复杂度最小,如果假设
N 个数通过管道流式输入的话,这个方法的空间复杂度是 O(K);