题解 | #寻找第K大#

最简单的方法就是排序，返回第n-k大的即可，此外可以使用最大堆，这些复杂度都是O(nlogn)的。 我在代码里自己写了一遍quicksort，mergesort，用python的sort试了一下，用最大堆试了一下，发现单纯用quicksort是不能行的，其他都是可以通过的。

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param a int整型一维数组 
# @param n int整型 
# @param K int整型 
# @return int整型
#
import heapq
class Solution:
    def findKth(self , a, n: int, K: int) -> int:
        # write code here
        # self.quicksort(a , 0 , n-1)
        a = self.mergesort(a)
        print(a)
        return a[n-K]

    def mergesort(self , a):
        if len(a)==0 or len(a) == 1:
            return a
        else:
            mid = len(a)//2
            tmp1 = self.mergesort(a[:mid])
            tmp2 = self.mergesort(a[mid:])
            p1 = p2 = 0
            new = []
            while p1<len(tmp1) or p2<len(tmp2):
                if p1 == len(tmp1):
                    new.append(tmp2[p2])
                    p2+=1
                elif p2==len(tmp2):
                    new.append(tmp1[p1])
                    p1+=1
                else:
                    if tmp1[p1] <= tmp2[p2]:
                        new.append(tmp1[p1])
                        p1+=1
                    else:
                        new.append(tmp2[p2])
                        p2+=1
            return new




    def quicksort(self , a , start , end):
        t = a[end]
        t_index = end
        i = start
        while i < t_index:
            if a[i] <= t:
                i+=1
            else:
                tmp = a[i]
                del a[i]
                a.insert(t_index , tmp)
                t_index -= 1
        if t_index>start+1:
            self.quicksort(a , start , t_index-1)
        if t_index+1 < end:
            self.quicksort(a,t_index+1,end)

    def findKth2(self , a, n: int, K: int) -> int:
        a.sort()
        return a[n-K]

    def findKth3(self , a, n: int, K: int) -> int:
        heapq.heapify(a)
        for i in range(n-K):
            heapq.heappop(a)
        return a[0]


a = [1,3,5,2,2] ; n = 5; K = 3
print(Solution().findKth(a , n , K))