具體鏈接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array/

在未排序的數(shù)組中找到第 k 個最大的元素。請注意，你需要找的是數(shù)組排序后的第 k 個最大的元素，而不是第 k 個不同的元素。

示例 1: 
 
輸入: [3,2,1,5,6,4] 和 k = 2 
輸出: 5 
示例 2: 
 
輸入: [3,2,3,1,2,4,5,5,6] 和 k = 4 
輸出: 4 

經(jīng)典的TopK問題還有：最大(小) K 個數(shù)、前 K 個高頻元素、第 K 個最大(小)元素

對此TopK問題本質(zhì)上是一個排序問題，排序算法一共有十個，這個還有很多排序算法沒有介紹過。

至于為什么TopK問題最佳的答案是堆排序?其實在空間和時間的復(fù)雜度來考量，雖說快排是最好的排序算法，但是對于100億個元素從大到小排序，然后輸出前 K 個元素值。

可是，無論我們掌握的是快速排序算法還是堆排序算法，在排序的時候，都需要將全部的元素讀入到內(nèi)存中。也就是說，100億個整型元素大約需要占用40GB的內(nèi)存空間，這聽起來就不像是普通民用電腦能干的事情，(一般的民用電腦內(nèi)存比這個小，比如我寫文章用的電腦內(nèi)存是 32GB)。

眾所周知，快速排序和堆排序的時間復(fù)雜度都可以達到，但是對于快速排序來說，數(shù)據(jù)是順序訪問的。而對于堆排序來說，數(shù)據(jù)是跳著訪問的。比如堆排序中，最重要的一個操作就是數(shù)據(jù)的堆化。因此，快速排序的時間復(fù)雜度是優(yōu)于堆排序的。

但是快速排序是新建數(shù)組，空間復(fù)雜度是，遠低于堆排序的。對于龐大的數(shù)據(jù)量，應(yīng)該優(yōu)先選擇堆排序。

如果使用heapq內(nèi)置模塊，尋找數(shù)組中的第K個最大元素就是一行代碼，heapq中的nlargest接口封裝好了，返回的是一個數(shù)組，需要切片取值。

import heapq 
class Solution: 
    def findKthLargest(self, nums: List[int], k: int) -> int: 
        return heapq.nlargest(k,nums)[-1] 

當(dāng)然，一般都是手寫堆排序，尋找數(shù)組中的第K個最大元素建立最小堆，尋找數(shù)組中的第K個最小元素建立最大堆，

思路：「取nums前K個元素建立大小為K的最小堆，后面就是維護一個容量為k的小頂堆，堆中的k個節(jié)點代表著當(dāng)前最大的k個元素，而堆頂顯然是這k個元素中的最小值?！?/strong>

class Solution: 
    def findKthLargest(self, nums: List[int], k: int) -> int: 
        heapsize=len(nums) 
        def maxheap(a,i,length): 
            l=2*i+1 
            r=2*i+2 
            large=i 
            if l<length and a[l]>a[large]: 
                large=l 
            if r<length and a[r]>a[large]: 
                large=r 
            if large!=i: 
                a[large],a[i]=a[i],a[large] 
                maxheap(a,large,length) 
             
        def buildheap(a,length): 
            for i in range(heapsize//2,-1,-1): 
                maxheap(a,i,length) 
 
        buildheap(nums,heapsize) 
        for i in range(heapsize-1,heapsize-k,-1): 
            nums[0],nums[i]=nums[i],nums[0] 
            heapsize-=1 
            maxheap(nums,0,heapsize) 
        return nums[0]