528
个编辑
更改
跳到导航
跳到搜索
第4行：
第4行： − + − 参考 Python 的实现：https://github.com/python/cpython/blob/3.9/Lib/heapq.py#L521+ + − * 先 push ''n'' 个元素到小根堆中（找前 ''n'' 小则用大跟堆）+ − * 对剩下的元素，和堆顶比较，若更大则替换堆顶+ + + + + + + + + +
无编辑摘要
* pop：O(log n)
* pop：O(log n)
== 找前 ''n'' 大的数 ==
== 找前 ''n'' 大的数（top K） ==
* 先 push ''n'' 个元素到小根堆中（找前 ''n'' 小则用大跟堆）
* 对剩下的元素，和堆顶比较，'''若更大'''则替换堆顶
<syntaxhighlight lang=python>
def topk(xs: list[int], k: int):
heap = []
for x in xs:
if len(heap) >= k:
if x > heap[0]:
heapq.heapreplace(heap, x)
else:
heapq.heappush(heap, x)
return heap
</syntaxhighlight>
[[Category:刷题]]
[[Category:刷题]]