题目链接
难度：中等 类型： 快排、堆
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例：
输入: [3,2,1,5,6,4], k = 2
输出: 5
解题思路
- 只冒k次泡会超时
- 建立一个大小为k的堆，所有数遍历一遍之后就有结果了
- 用快排，排完一趟后，如果右半边长度大于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)
