题解 | #寻找第K大#

方法一：排序：

class Solution:
    def findKth(self , a: List[int], n: int, K: int) -> int:
            a = sorted(a, reverse=True)
            return a[K-1]

方法二：小顶堆+相反数：

import heapq
class Solution:
    def findKth(self , a: List[int], n: int, K: int) -> int:
         heap = []
         for i in range(n):
             heapq.heappush(heap, -a[i]) # 小顶堆存进去负数
         for i in range(K-1):
             heapq.heappop(heap) #出队前K-1个（最大的）
         return -heapq.heappop(heap) # 相反数

方法三：快速排序：

class Solution:
    def findKth(self , a: List[int], n: int, K: int) -> int:
         return self.quickSort(a, 0, n-1, K)

    def quickSort(self, a, start, end, k):
        if start>end:
            return -1
        pivot = a[start]
        left,right = start,end
        while left<right: # 和下面的小于号一致
            while left<right and a[right]<=pivot: # 由大到小
                right -= 1
            while left<right and a[left]>=pivot:
                left += 1
            if left!=right:
                a[left],a[right] = a[right],a[left]
        a[left],a[start] = a[start],a[left] # 最后left是比pivot大的
        if left==k-1: # 是序号，第k个
            return a[left]
        elif left<k-1:
            return self.quickSort(a, left+1, end, k)
        else:
            return self.quickSort(a, start, left-1, k)