【数据结构与算法】【LeetCode】【排序】215.数组中的第K个最大的元素

class Solution:
    def findKthLargest(self, nums, k) -> int:
        self.quick_sort(nums,0,len(nums))
        return nums[len(nums)-k]
    def quick_sort(self,nums,lo,hi):
        if lo+1>=hi:
            return 
        first =lo
        last =hi-1
        pivot=nums[first]
        while first<last:
            while first<last and nums[last]>=pivot:
                last = last-1
            nums[first]=nums[last]
            while first<last and nums[first]<=pivot:
                first=first+1
            nums[last] = nums[first]
        nums[first]=pivot
        self.quick_sort(nums,lo,first)
        self.quick_sort(nums,first+1,hi)

a = Solution()
nums=[3,2,3,1,2,4,5,5,6]
k = 2
a.findKthLargest(nums,k)

import random
class Solution:
    def findKthLargest(self, nums, k) -> int:
        target = len(nums)-k
        lo = 0
        hi = len(nums)-1
        while lo<=hi:
            p = self.partion(nums,lo,hi)
            if p<target:
                lo=p+1
            elif p>target:
                hi =p-1
            else:
                return nums[p]

    def partion(self,nums,lo,hi):
        if lo<hi: # 随机选取pivot
            rindex= random.randint(lo,hi)
            nums[lo],nums[rindex]=nums[rindex],nums[lo]
        pivot = nums[lo]
        while lo<hi:
            while lo<hi and nums[hi]>=pivot:
                hi=hi-1
            nums[lo]=nums[hi]
            while lo<hi and nums[lo]<=pivot:
                lo = lo+1
            nums[hi]=nums[lo]
        nums[lo]=pivot
        return lo

a = Solution()
nums=[3,2,3,1,2,4,5,5,6]
k = 2
a.findKthLargest(nums,k)

import random
class Solution:
    def findKthLargest(self, nums, k) -> int:
        target = len(nums)-k
        lo = 0
        hi = len(nums)-1
        while lo<=hi:
            p = self.partion(nums,lo,hi)
            if p<target:
                lo=p+1
            elif p>target:
                hi =p-1
            else:
                return nums[p]

    def partion(self,nums,lo,hi):
        random_index = random.randint(lo,hi)
        nums[random_index],nums[lo]=nums[lo],nums[random_index]
        pivot = nums[lo]
        j=lo
        for i in range(lo+1,hi+1):
            if nums[i]<pivot:
                j+= 1
                nums[i],nums[j]=nums[j],nums[i]
        nums[lo],nums[j]=nums[j],nums[lo]
        return j

a = Solution()
nums=[3,2,3,1,2,4,5,5,5,6,6]
k = 2
a.findKthLargest(nums,k)