Leetcode215-数组中的第K个最大元素-Python实现

• 题目要求：

• 思路：

  • 维护一个小根堆（父节点的值小于或等于子节点的值），小根堆拥有的节点数量是 k，保持小根堆始终有 k 个元素。
  • 遍历数组，把当前元素加入到堆中，加入后判断堆的节点数量，如果大于 k，把最小的元素取出，从堆中删除，这样保持堆中剩余的始终是最大的 k 个元素，堆顶是这些数字中最小的，也就是第 k 大的元素。

• Python heapq 参考：

  • https://docs.python.org/zh-tw…
• 核心代码：

# 小根堆用数组代替
res = []
# 遍历数组
for i in nums:
    # 把当前元素添加到堆中，保持小根堆
    heapq.heappush(res,i)
    # 如果堆中的元素数量，也就是数组的长度大于 k
    if len(res) > k:
        # 把堆顶元素取出，也就是把最小的元素取出堆
        heapq.heappop(res)
# 如果 res 不为空，就返回 res[0], 如果 res 为空，说明最开始的数组就为空，返回 None
return res[0] if res else None

• 完整代码：

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        res = []
        for i in nums:
            heapq.heappush(res,i)
            if len(res) > k:
                heapq.heappop(res)
        return res[0] if res else None