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

lsmCC

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

FishC

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

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

import heapq

def find_kth_largest(nums, k):
    heap = []

    for num in nums:
        heapq.heappush(heap, num)
        if len(heap) > k:
            heapq.heappop(heap)

    return heap[0]

def find_kth_smallest(nums, k):
    heap = []

    for num in nums:
        heapq.heappush(heap, -num)  # 取负数使得最大值成为堆的根节点
        if len(heap) > k:
            heapq.heappop(heap)

    return -heap[0]

# 示例用法
nums = [3, 1, 4, 1, 5, 9, 2, 6, 5]
k = 2

kth_largest = find_kth_largest(nums, k)
print(f"The {k}th largest number is: {kth_largest}")

kth_smallest = find_kth_smallest(nums, k)
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 小助理，如未能正确解答您的问题，请继续追问。