数据结构与算法 · 单选题 · 第 53 题
计算机基础面试八股 · 第 53 题
要从 n 个数中找出最大的 k 个数(k 远小于 n),常用且高效的做法是?
- A维护一个大小为 k 的大顶堆,时间复杂度 O(n log k)
- B用一个栈把所有元素依次压入,再依次弹出前 k 个
- C维护一个大小为 k 的小顶堆,时间复杂度 O(n log k)
- D把所有元素插入一个单链表,再从表头取出前 k 个
答案
C C. 维护一个大小为 k 的小顶堆,时间复杂度 O(n log k)
解析
小顶堆的堆顶是当前 k 个候选里最小的,新元素比堆顶大就替换堆顶并调整,遍历结束后堆里就是最大的 k 个。用大顶堆维护 k 个元素时,无法快速知道该淘汰哪个,方向反了。如果允许修改数组,也可以用快速选择算法,平均 O(n)。