LeetCode TopK问题题解

LeetCode TopK问题题解题目描述找到数组中第 K 大的元素。示例输入nums [3,2,1,5,6,4],k 2输出5解题思路方法堆思路使用最小堆维护前 k 大的元素。遍历数组将每个元素加入堆中。如果堆的大小超过 k则弹出堆顶元素。最后堆顶元素就是第 k 大的元素。复杂度分析时间复杂度O(n log k)空间复杂度O(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 test_find_kth_largest(): nums [3, 2, 1, 5, 6, 4] k 2 print(find_kth_largest(nums, k)) # 输出5 if __name__ __main__: test_find_kth_largest()总结TopK问题是堆的典型应用通过维护一个大小为 k 的堆来找出第 k 大的元素。