10亿个数中取前1000大的数,写个python demo,要求简单易懂

bluesky1年前 ⋅ 692 阅读
我们可以使用堆来解决这个问题。我们可以先遍历这10亿个数,把前1000个数加入一个小根堆中。之后,遍历剩余的数,如果当前数比堆顶元素大,则用当前元素替换堆顶元素,并重新构建小根堆。当遍历完10亿个数之后,堆中存储的就是前1000大的数了。

下面是Python代码实现:

```python
import heapq

def find_top_k(nums, k):
    heap = nums[:k]
    heapq.heapify(heap)
    for num in nums[k:]:
        if num > heap[0]:
            heapq.heapreplace(heap, num)
    return heap

# 测试代码
nums = list(range(1000000000))
top_k = find_top_k(nums, 1000)
print(top_k)
```

我们先用`heapq.heapify`将前1000个数构建成一个小根堆。之后遍历剩余的数,如果当前数比堆顶元素大,则使用`heapq.heapreplace`将堆顶元素替换成当前数,重新构建小根堆。最后返回堆中的前k个元素。

全部评论: 0

    相关推荐