215. 数组中的第K个最大元素 小顶堆解

原题：

Find the kth largest element in an unsorted array.
Note that it is the kth largest element in the sorted order,
not the kth distinct element.

大概意思：

在未排序的数组中找到第 k 个最大的元素。

注：你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

解题思路

这道题乍一看还是挺简单的，用sort()排序，然后切片，就行了。

不过仔细想想，时间复杂度是不是挺大的，尽管sort()采用了二分排序法，但时间复杂度依然为
O(n*logn)，还是挺高的。

这道题的典型做法是采用最小顶堆。也就是堆算法，python有一个库函数，heapq就封装了6种关于最小顶堆的方法。

这里来详细介绍一下三种方法：

法一：

首先很容易想到的是sort()的方法，但是难度为中等的题目应该不至于这样。

sort()方法的时间复杂度为O(N*logN),空间复杂度为O(1)，因为就地排序

法二：

这道题可以使用堆来优化，堆比较列表的优势在于，它可以在插入数据时自动调整位置，使之符合堆特征，即nums[i]总是大于nums[i//2]。这里顺便复习下heap的各个函数用法：

1.heappush(heap, x) 将x压入堆中

2.heappop(heap) 从堆中弹出最小的元素

3.heapify(heap) 让列表具备堆特征

4.heapreplace(heap, x) 弹出最小的元素，并将x压入堆中，返回弹出的元素

5.nlargest(n, iter) 返回iter中n个最大的元素

6.nsmallest(n, iter) 返回iter中n个最小的元素

其中法二就是采用nlargest直接获取答案

法三：

利用最大堆，存储前k个最大的数，最后返回堆底元素就行了。

主要思路：

①当i<k,压数据进堆。

②当i>=k，比较sums[i]和堆底元素，如果大于，则使用heapreplace进行替换，否则跳过。

代码：

法一：

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        from heapq import heappush,heapreplace
        # 普通的sort()方法
        # 时间复杂度O(N*logN),空间复杂度O(1)
        nums.sort()
        return nums[-k]

法二

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        from heapq import heappush,heapreplace
        # 使用堆的nlargest(n,iter)返回前n个最大的数,倒序排练
        return nlargest(k,nums)[-1]

法三

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        from heapq import heappush,heapreplace
        # 使用小顶堆
        heap = []
        for i in range(len(nums)):
            if i < k:
                heappush(heap,nums[i])
            else:
                if nums[i] > heap[0]:
                    m = heapreplace(heap,nums[i])
		# 返回顶部元素
        return heap[0]

题目来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array