分治法学习

class Solution(object):

    
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """

        def partition(l, r):
            pivot = nums[l]
            while l<r:
                while l<r and nums[r] <= pivot:
                    r-=1
                nums[l] = nums[r]
                while l<r and nums[l] >= pivot:
                    l+=1
                nums[r] = nums[l]
            nums[l] = pivot
            return l
        def find_K(l, r , k):
            if l>r: return
            pivot = partition(l, r)
            if pivot==k: return
            if k < pivot: 
                find_K(l, pivot-1, k)
            else:
                find_K(pivot+1, r, k)
        k-=1
        find_K(0, len(nums)-1, k)
        return nums[k]