“Heap”的版本间的差异
跳到导航
跳到搜索
| （未显示同一用户的1个中间版本） | |||
| 第4行： | 第4行： | ||
* pop：O(log n) | * pop：O(log n) | ||
| − | == 找前 ''n'' | + | == 找前 ''n'' 大的数（top K） == |
| − | + | * 先 push ''n'' 个元素到小根堆中（找前 ''n'' 小则用大跟堆） | |
| + | * 对剩下的元素，和堆顶比较，'''若更大'''则替换堆顶 | ||
| − | + | 时间复杂度 O(n logk)。 | |
| − | + | <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:刷题]] | ||
2022年10月8日 (六) 13:49的最新版本
时间复杂度
- push：最坏 O(log n)，平均 O(1)
- pop：O(log n)
找前 n 大的数（top K）
- 先 push n 个元素到小根堆中（找前 n 小则用大跟堆）
- 对剩下的元素，和堆顶比较，若更大则替换堆顶
时间复杂度 O(n logk)。
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