快速选择能否直接找出数组中第 K 个最大元素？
摘要：本题在线练习：LeetCode 215. 数组中的第K个最大元素 - 在线练习（免费 · 无需登录 · AI 辅助）(https:onefly.topzero2Leetcodepl
本题在线练习：LeetCode 215. 数组中的第K个最大元素 - 在线练习（免费 · 无需登录 · AI 辅助）(https://onefly.top/zero2Leetcode/playground.html?id=215)
配套刷题网站 Zero2Leetcode —— 内置本地 OJ + AI 教练，零门槛开始刷 Hot 100。
题目概述
给定整数数组 nums 和整数 k，返回数组中第 k 个最大的元素。
注意：是“按大小排序后的第 k 个”，不是第 k 个不同的元素。
核心思路：Quickselect（快速选择）只做必要的分区
如果直接排序，时间复杂度是 O(n log n)，一定能过，但不是最优。
Quickselect 的思想：
使用“快速排序的 partition 操作”把数组分成两部分
partition 后，某个位置 p 上的元素已经是最终有序数组中的正确位置
如果 p 正好是目标下标，直接返回
否则只在目标所在的那一边继续做 partition
平均时间复杂度 O(n)。
第 k 大转换成“第 n-k 小”（0-based）：
target = len(nums) - k
代码实现（Python）：随机化 Quickselect（平均 O(n)）
import random
from typing import List
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
target = len(nums) - k # 第 k 大 = 第 (n-k) 小（0-based）
def partition(l: int, r: int, pivot_index: int) -> int:
pivot = nums[pivot_index]
nums[pivot_index], nums[r] = nums[r], nums[pivot_index]
store = l
for i in range(l, r):
if nums[i] < pivot:
nums[store], nums[i] = nums[i], nums[store]
store += 1
nums[store], nums[r] = nums[r], nums[store]
return store
l, r = 0, len(nums) - 1
while True:
pivot_index = random.randint(l, r)
p = partition(l, r, pivot_index)
if p == target:
return nums[p]
if p < target:
l = p + 1
else:
r = p - 1
逐行拆解
target = len(nums) - k
把“第 k 大”转为“第 target 小”，这样 partition 用 < pivot 的逻辑就很自然。
if nums[i] < pivot:
swap(...)
partition 的结果是：
[l, store-1] 都 < pivot
store 是 pivot 的最终位置
[store+1, r] 都 >= pivot
if p == target: return nums[p]
一旦 pivot 的最终位置刚好是目标下标，答案就出来了，不必再处理其它元素。