BM47. 寻找第K大
题目描述
有一个整数数组 a，请你根据快速排序的思路，找出数组中第 K 大的数。 给定数组 a、大小 n 和要找的 K，请返回第 K 大的数（包含重复的元素，不去重）， 保证答案存在。
输入格式
a：int 型一维数组；n：int 型，数组长度；K：int 型，要找第 K 大。
输出格式
返回 int 型，第 K 大的数（含重复元素）。
示例
示例 1
输入：
a = [1,3,5,2,2], n = 5, K = 3
输出：
2
说明：
升序为 [1,2,2,3,5]，第 3 大（从大到数）是 2。
示例 2
输入：
a = [10,10,9,9,8,7,5,6,4,3,4,2], n = 12, K = 3
输出：
9
说明： 去重后的第 3 大是 8，但本题要求包含重复元素，不去重，所以输出 9。
解题思路
第一步：理解问题本质
「第 K 大（含重复）」= 把数组升序排序后，第 n - K 个元素（下标从 0 起）。
例如 n=5、K=3，就是排序后的下标 2。
关键是不去重：不能先 set 再取，否则结果会偏大。
第二步：直接排序
return sorted(a)[n - K]
O(n log n)，思路最直白，但题目提示要「根据快速排序的思路」， 用快速选择更快。
第三步：快速选择（Quickselect）
快速选择是「只做一半的快排」：
- 选一个基准
pivot，做一次三路划分，把数组分成三段： 小于 pivot、等于 pivot、大于 pivot； - 目标下标
target = n - K：- 若落在「小于」段，只递归处理左半；
- 若落在「大于」段，只处理右半；
- 若落在「等于」段，说明 pivot 就是答案，直接返回。
每次只处理一侧，规模期望减半，平均 O(n)。 用三路划分（而不是普通两路）是因为数组含大量重复 —— 两路划分在「全相等」时会退化成 O(n²)，三路则一次就把等于段整体定位。
完整代码实现
算法可视化 · 逐帧回放这道题的代码99 帧 · 录制输入 [10,10,9,9,8,7,5,6,4,3,4,2], 12, 3
from typing import List
class Solution:
def findKth(self, a: List[int], n: int, K: int) -> int:
"""原地快速选择，返回升序第 n-K 个元素（即第 K 大）"""
target = n - K # 第 K 大 == 升序里下标 n-K 的元素
lo, hi = 0, n - 1
while True:
pivot = a[(lo + hi) // 2]
lt, i, gt = lo, lo, hi # 三路划分：<pivot 放左边，>pivot 放右边
while i <= gt:
if a[i] < pivot:
a[lt], a[i] = a[i], a[lt]
lt += 1
i += 1
elif a[i] > pivot:
a[gt], a[i] = a[i], a[gt]
gt -= 1
else:
i += 1
if target < lt:
hi = lt - 1
elif target > gt:
lo = gt + 1
else:
return pivot
示例推演
以 a = [1,3,5,2,2], n = 5, K = 3 为例，target = 2：
| 轮次 | 区间 | pivot | 划分后（< | = | >） | target=2 落在 | |------|------|-------|---------------------|----------------| | 1 | [0,4] | 5 | [1,3,2,2] , [5] | 落在「< 5」段（下标 0..3） | | 2 | [0,3] | 3 | [1,2,2] , [3] | 落在「< 3」段（下标 0..2） | | 3 | [0,2] | 2 | [1] , [2,2] , [] | target=2 落在「= 2」段 → 返回 2 |
结果 2，与答案一致。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 排序 | O(n log n) | O(n) | 最简单 |
| 快速选择 | 平均 O(n) | O(1) | 推荐，原地 |
| 快速选择（最坏） | O(n²) | O(1) | 基准选得极差时 |
易错点总结
1. 下标换算搞反
「第 K 大」对应升序下标 n - K，不是 K - 1。写错会取到第 K 小。
2. 去了重
题目要求包含重复元素，两个相同的值各占一个名次，别用 set。
3. 用两路划分
普通两路划分遇到大量重复（如全相等）会退化。用三路划分更稳。
扩展思考
- 「第 K 小」只差一个下标换算：升序下标
K - 1。 - 若要「第 K 大的 k 个数」，直接用小顶堆维护 k 个（BM46）。