LeetCode 215. 数组中的第K个最大元素

题目描述

未排序的数组，返回其排序后的第 K 个最大元素。

样例：
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

算法

(扫描一遍 维护一个小根堆） O(n∗logk)
遍历数组，维护一个大小为K的小根堆
为什么是小根堆，堆顶元素是堆中最小，那么还在堆中的都比它大，没在堆内的都比它小。
堆中有k个元素，那么他自然就是第K的最大元素了
找最大，用小根
注意：优先队列默认的是大根堆，所以声明的时候注意参数。

复杂度

时间复杂度

线性扫描 O(n∗logk)

空间复杂度

额外的小根堆 O(k)

python code

from heapq import *
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        h = []
        for num in nums:
            heappush(h, num)
            if len(h) > k: heappop(h)
        return h[0]