机试刷题_寻找第K大【python】

题目：寻找第K大

描述
有一个整数数组，请你根据快速排序的思路，找出数组中第 k 大的数。

给定一个整数数组 a ,同时给定它的大小n和要找的 k ，请返回第 k 大的数(包括重复的元素，不用去重)，保证答案存在。

from operator import le
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param a int整型一维数组 
# @param n int整型 
# @param K int整型 
# @return int整型
#
class Solution:
    def partition(self,nums,left,right):
        i = left
        j = right
        while i<j:
            while i<j and nums[j] >= nums[left]:
                j -= 1
            while i<j and nums[i] <= nums[left]:
                i += 1
            nums[i],nums[j] = nums[j],nums[i]
        nums[i],nums[left] = nums[left],nums[i]
        return i

    def quickSort(self,nums,left,right):
        # 子数组长度为 1 时终止递归
        if left >= right:
            return 
        # 哨兵划分
        base = self.partition(nums,left,right)

        self.quickSort(nums,left,base-1)
        self.quickSort(nums,base+1,right)

    def findKth(self , a: List[int], n: int, K: int) -> int:
        # 快排
        self.quickSort(a,0,n-1)
        print(a)
        return a[n-K]