求O(n*log(k))时间复杂度的数组第k大元素及Python实现思路

核心方案：最小堆（小顶堆） #

维护一个固定大小为k的最小堆，堆顶元素是当前堆内的最小值。遍历数组时遵循以下规则：

• 当堆的元素数量小于k时，直接将当前元素加入堆
• 当当前元素大于堆顶元素时，弹出堆顶，把当前元素压入堆
  遍历完成后，堆顶元素就是数组的第k大元素。

Python代码实现 #

利用Python内置的heapq模块（默认实现最小堆），可以快速完成：

import heapq

def find_kth_largest(nums, k):
    min_heap = []
    for num in nums:
        heapq.heappush(min_heap, num)
        # 保持堆的大小不超过k
        if len(min_heap) > k:
            heapq.heappop(min_heap)
    # 堆顶即为第k大元素
    return min_heap[0]

# 测试示例
test_nums = list(range(1, 10))  # 生成[1,2,3,4,5,6,7,8,9]
print(find_kth_largest(test_nums, 2))  # 输出：8

复杂度验证 #

• 遍历数组共执行n次操作，每次堆的push/pop操作时间复杂度为O(logk)（因为堆的大小始终维持在k以内）
• 总时间复杂度为O(n·logk)，满足需求；空间复杂度为O(k)，仅需存储k个元素。

方案优势对比 #

如果用最大堆存储全部元素再弹出k次，时间复杂度为O(n + k·logn)，当k接近n时，复杂度会退化为O(n·logn)，效率不如最小堆。而最小堆始终只维护k个元素，在空间和时间效率上更优。

内容的提问来源于stack exchange，提问作者Displayed Name