【LeetCode】215. Kth Largest Element in an Array

【Description】
Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example 1:

Input: [3,2,1,5,6,4] and k = 2
Output: 5
Example 2:

Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4
Note:
You may assume k is always valid, 1 ≤ k ≤ array's length.

【Idea】
忘了在哪儿刷到必须要用快排做的题，麻蛋累死 = =
在原快排基础上，需要用二分简化不必要计算，mid处做判断。
没啥难的，就是较劲。。。。。。。堆不香吗

【Solution】

快排+二分
class Solution:
    def partition(self, nums, left, right):
        pivot = right
        i = left
        for j in range(left, right):
            if nums[j] < nums[right]:
                nums[i], nums[j] = nums[j], nums[i]
                i += 1
        nums[i], nums[pivot] = nums[pivot], nums[i]
        return i

    def recursion(self, nums, left, right, k):
        if left >= right:
            return 
        mid = self.partition(nums, left, right)
        if len(nums)-mid < k:        # >mid的数比k少，则nums[mid]是第k+i个最大数,需要在左子数组找
            self.recursion(nums, left, mid-1,k)
        if len(nums)-mid > k:
            self.recursion(nums, mid+1, right,k)
        

    def findKthLargest(self, nums: List[int], k: int) -> int:
        left, right = 0, len(nums)-1
        self.recursion(nums, left, right,k)
        return nums[-k]

image.png