题解 | #寻找第K大#

随机取基准值pivot,减少时间消耗,避免超时.

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param a int整型一维数组 
# @param n int整型 
# @param K int整型 
# @return int整型
#
class Solution:
    def quickSort(self,nums,K):
        res = self.partition(nums, 0, len(nums) - 1,K)
        if res:
            return res
        else:
            return nums[K-1]

    def partition(self,nums, left, right,K):
        import random
        if left >= right:
            return
        # 随机取pivot,避免超时
        pivot = random.randint(left, right)
        equal = self.sortpivote(nums, nums[pivot], left, right)
        if equal[0] >= K:
            self.partition(nums, left, equal[0] - 1,K)
        elif equal[1] < K:
            self.partition(nums, equal[1], right,K)
        else:
            return nums[equal[0]+1]

    def sortpivote(self,nums, pivot, left, right):
        less = left - 1
        more = right + 1
        i = left
        while i < more:
            if nums[i] > pivot:
                less += 1
                nums[i], nums[less] = nums[less], nums[i]
                i += 1
            elif nums[i] < pivot:
                more -= 1
                nums[i], nums[more] = nums[more], nums[i]
            else:
                i += 1
        return [less + 1, more - 1]
    
    def findKth(self , a: List[int], n: int, K: int) -> int:
        return self.quickSort(a,K)
        # write code here