题解 | #寻找第K大#

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param a int整型一维数组 
# @param n int整型 
# @param K int整型 
# @return int整型
class Solution:
    def __partition(self,li,left,right):
        num = li[left] # 需要归为的数
        '''
        左边有空位，从右边开始找比num小的放左边空位
        这时右边有空位了，同理
        while终止：碰到或者找需要移位的
        '''
        while left < right:
            while left < right and li[right] >= num:
                # 没碰到并且不满足移位条件
                # 等于的时候需要移动指针，不然就死循环了
                right -= 1
            li[left] = li[right]

            while left < right and li [left] <= num:
                left += 1
            li[right] = li[left]
        li[left] = num
        return left

    def findKth(self , a: list[int], n: int, K: int) -> int:
        # write code here
        K = n-K
        low = 0
        high = n-1
        cur = self.__partition(a,low,high)
        while cur != K:
            if cur < K:
                low = cur+1
            else:
                high = cur-1
            cur = self.__partition(a,low,high)
        return a[cur]