題目鏈接
難度：中等 ??????類型： 快排呵晨、堆
給定整數(shù)數(shù)組 nums 和整數(shù) k磺陡，請(qǐng)返回?cái)?shù)組中第 k 個(gè)最大的元素揖庄。
請(qǐng)注意墨吓，你需要找的是數(shù)組排序后的第 k 個(gè)最大的元素置蜀，而不是第 k 個(gè)不同的元素东且。
你必須設(shè)計(jì)并實(shí)現(xiàn)時(shí)間復(fù)雜度為 O(n) 的算法解決此問題接癌。
示例：
輸入: [3,2,1,5,6,4], k = 2
輸出: 5
解題思路
- 只冒k次泡會(huì)超時(shí)
- 建立一個(gè)大小為k的堆，所有數(shù)遍歷一遍之后就有結(jié)果了
- 用快排邮利，排完一趟后弥雹，如果右半邊長(zhǎng)度大于k，就在右半邊找延届；右半邊長(zhǎng)度小于k剪勿，就在左半邊找；等于k就返回第k個(gè)
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)
