大小根堆维护第k大的数跟第k小的数代码

lsmCC

大小根堆维护第k大的数跟第k小的数代码怎么写的

FishC

维护第k大的数可以使用最小堆（小根堆），维护第k小的数可以使用最大堆（大根堆）。

下面是使用Python实现维护第k大的数和第k小的数的代码示例：

1. import heapq
   
2. 
   
3. def find_kth_largest(nums, k):
   
4.     heap = []
   
5. 
   
6.     for num in nums:
   
7.         heapq.heappush(heap, num)
   
8.         if len(heap) > k:
   
9.             heapq.heappop(heap)
   
10. 
    
11.     return heap[0]
    
12. 
    
13. def find_kth_smallest(nums, k):
    
14.     heap = []
    
15. 
    
16.     for num in nums:
    
17.         heapq.heappush(heap, -num)  # 取负数使得最大值成为堆的根节点
    
18.         if len(heap) > k:
    
19.             heapq.heappop(heap)
    
20. 
    
21.     return -heap[0]
    
22. 
    
23. # 示例用法
    
24. nums = [3, 1, 4, 1, 5, 9, 2, 6, 5]
    
25. k = 2
    
26. 
    
27. kth_largest = find_kth_largest(nums, k)
    
28. print(f"The {k}th largest number is: {kth_largest}")
    
29. 
    
30. kth_smallest = find_kth_smallest(nums, k)
    
31. print(f"The {k}th smallest number is: {kth_smallest}")

复制代码

以上代码中，我们使用了`heapq`模块中的`heappush`和`heappop`函数来实现堆的插入和删除操作。对于维护第k大的数，我们使用最小堆，每次插入一个数后，如果堆的大小超过k，则弹出堆顶元素；对于维护第k小的数，我们使用最大堆，每次插入一个数后，如果堆的大小超过k，则弹出堆顶元素。最后返回堆中的根节点即可得到第k大或第k小的数。

以上代码在示例用法中给出了一个具体例子，nums是要统计的数字列表，k是期望找到的第k大或第k小的数。输出分别是第k大和第k小的数。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。