IT 面试题库

求 Top K 时,堆排序和快速选择分别怎么选?为什么小顶堆能做到 O(n log k)?

中级编程题算法工程师后端开发工程师TopK堆快速选择优先队列

题目

考察经典 Top K 问题的数据结构选择、复杂度和工程取舍。

参考答案

内容深度:适中 · 含示例/代码 · 来源:外部链接 · 未复核 · 29 天前更新

小顶堆做法

快速选择(Quickselect)

怎么选

代码要点

import heapq
def topk(nums, k):
    h = []
    for x in nums:
        if len(h) < k: heapq.heappush(h, x)
        elif x > h[0]: heapq.heapreplace(h, x)
    return h

常见坑

练这道题

同分类 · 高频题

题目与答案就在本页;收藏、批注和错题重练在应用内

这道题看完了?连刷同类题,趁热打铁效果最好 进入刷题