在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。 解题思路 用堆排序来解决这个问题——建立一个大根堆，做 k - 1次删除操作后堆顶元素就是我们要找的答案。 1、构建一棵完全二叉树，从第一个非叶子节点为根节点的子树开始，将其调整为大根堆。 2、调整倒数第二个非叶子节点作为根节点的子树，调整倒数第三个非叶子节点作为根节点的子树…调整倒数第K个非叶子节点作为根节点的子树，直到调整完成。 3、删除k-1次堆顶元素（每一次删除堆顶元素后将末尾节点（从右节点开始）补充到堆顶后再进行调整） 4、第k-1次删除后，末尾补充调整后，返回堆顶元素。 5、注意：堆排序只需要排序最后k位。 6、对于任意节点i，其左叶子节点为 2i+1,右叶子节点为 2i+2
代码
class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: def heapify(a, start, end): """ 自上向下堆化 Args: a (list): 输入数组 start (int): 堆化目标在数组的位置 end (int): 堆在数组的截止位置 """ while True: #初始化最大值所在位置为目标所在 max_pos = start # 如果左叶子节点存在，且大于目标值，则将最大值所在位置指向该节点所在位置 if start*2 + 1 <= end and a[start] < a[start*2+1]: max_pos = start*2 + 1 # 如果右叶子节点存在，且大于目标值，则将最大值所在位置指向该节点所在位置 if start*2 + 2 <= end and a[max_pos] < a[start*2+2]: max_pos = start*2 + 2 # 如果目标即为最大，完成该节点堆化，跳出循环 if max_pos == start: break # 交换位置，将最大值 a[start], a[max_pos] = a[max_pos], a[start] start = max_pos # 建堆,只需要对前半节点堆化 for i in range(len(nums)//2-1, -1, -1): heapify(nums, i, len(nums)-1) # 排序，只需要循环K次，排序TOP K个节点 i = len(nums) - 1 while i > len(nums) - 1 - k: nums[0], nums[i] = nums[i], nums[0] i -= 1 heapify(nums, 0, i) return nums[len(nums)-k]