LeetCode-python 215.数组中的第K个最大元素

题目链接
难度：中等       类型： 快排、堆

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例：

输入: [3,2,1,5,6,4], k = 2
输出: 5

解题思路

1. 只冒k次泡会超时
2. 建立一个大小为k的堆，所有数遍历一遍之后就有结果了
3. 用快排，排完一趟后，如果右半边长度大于k，就在右半边找；右半边长度小于k，就在左半边找；等于k就返回第k个

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        n = len(nums)
        left, right = 0, n - 1
        pivot = nums[left]

        while left < right:
            while nums[right] >= pivot and left < right:
                right -=1
            nums[left] = nums[right]

            while nums[left] <= pivot and left < right:
                left += 1
            nums[right] = nums[left]

        nums[left] = pivot

        if n - left == k:
            return nums[left]
        elif n - left > k:
            return self.findKthLargest(nums[left+1:], k)
        else:
            return self.findKthLargest(nums[:left], k + left - n)