数组中的第K个最大元素
Kth Largest Element in an Array
本机进度仅保存在当前浏览器
题目描述
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。注意是排序后第 k 个最大的元素，不是第 k 个不同的元素。要求不使用排序库完成（进阶：O(n) 时间）。
示例：nums = [3, 2, 1, 5, 6, 4]，k = 2，输出 5。
解题思路
- 建大小为 k 的小顶堆扫一遍是 O(n log k) 的稳当解法；达到 O(n) 平均要用快速选择。
- 快速选择是快排的变体：partition 后基准落在最终位置 p，若 p == 目标位直接返回，否则只递归包含目标的一侧。
- 目标下标为 len(nums) - k（升序第 k 大的位置）；每轮期望丢弃一半数据，平均 O(n)，最坏 O(n^2)（随机选 pivot 可避免）。
参考实现
查看参考实现Python · 建议先自行作答
import random
def findKthLargest(nums, k):
# 快速选择：只递归包含目标位置的一侧
target = len(nums) - k
l, r = 0, len(nums) - 1
while True:
pivot = nums[random.randint(l, r)]
i, j = l, r
while i <= j:
while nums[i] < pivot:
i += 1
while nums[j] > pivot:
j -= 1
if i <= j:
nums[i], nums[j] = nums[j], nums[i]
i += 1
j -= 1
if target <= j:
r = j
elif target >= i:
l = i
else:
return nums[target]