题目
给一个长度为
N 的
有重复元素的数组，输出第
10 大的数。要求注意合法性校验、边界条件与异常处理。
输入: nums = [23, 7, 45, 12, 45, 8, 33, 12, 19, 5, 45, 27, 12, 9, 33, 16, 41, 3]
输出: 16 （不去重口径）
8 （去重口径）
同题在 LeetCode 上是
LC 215 数组中的第 K 个最大元素，
k 是参数化的。
本题真正难的既不是算法也不是堆，是「第 10 大」这四个字在有重复元素时有两种完全不同的解释。
一、核心洞察：先问「去重吗」
拿主例的降序排列看一眼：
45, 45, 45, 41, 33, 33, 27, 23, 19, 16, 12, 12, 12, 9, 8, 7, 5, 3
↑ 第 10 个
- 不去重（LeetCode 215 的语义）：降序第
K 个，即下标 K-1。第 10 大 = 16。
- 去重（distinct 值里第
K 大）：45, 41, 33, 27, 23, 19, 16, 12, 9, 8, ...，第 10 大 = 8。
16 对 8，正好一倍。 同一个数组、同一句题面，答案取决于一个没被说出来的约定。而且两种约定都有道理：统计「第 10 高的分数」时通常想去重（并列第一不算占两个名额），统计「第 10 个订单金额」时不想去重（每笔订单都是独立的）。
面试里的正确动作：先问一句「重复元素算一次还是算多次」。 如果面试官说「都可以」，那就把两种都写出来、都测一遍 —— 这比猜对一个更得分。
这题还有个隐藏的连带问题：
去重口径下可能无解。 主例有 13 个不同值，够用；但如果数组是
[5,5,5,5,5]、要找第 3 大，distinct 只有 1 个 —— 这时候应该返回
null / 抛异常，而不是硬返回一个数。不去重口径则不存在这个问题（
N >= k 就有解）。
二、拆解：size-k 最小堆，O(n log k)
不需要把整个数组排序。维护一个
只有 k 个位置的最小堆，堆顶就是「当前第
k 大」：
- 堆没满（
< k 个）：直接入堆，向上调整；
- 堆已满且
v > 堆顶：挤掉堆顶，v 坐到堆顶后向下调整；
- 否则（
v <= 堆顶）：连前 k 大都进不去，O(1) 丢掉。
扫完之后堆里就是「见过的最大的
k 个值」，堆顶即答案。
import heapq
def kth_largest(nums, k, dedupe=False):
if nums is None:
raise ValueError("nums 不能为 None")
if not isinstance(k, int) or k <= 0:
raise ValueError("k 必须是正整数")
if len(nums) < k:
raise ValueError(f"数组长度 {len(nums)} 小于 k={k}")
heap = [] # 最小堆，heap[0] 就是当前第 k 大
seen = set() # 去重口径：堆里有哪些值
for v in nums:
if dedupe and v in seen:
continue
if len(heap) < k:
heapq.heappush(heap, v)
seen.add(v)
elif v > heap[0]:
if dedupe:
seen.discard(heap[0])
heapq.heapreplace(heap, v)
seen.add(v)
# else: v <= 堆顶，丢掉
if len(heap) < k:
raise ValueError(f"不同值只有 {len(seen)} 个，凑不齐第 {k} 大")
return heap[0]
去重口径为什么要额外维护
seen：只靠「
v > 堆顶」判断是不够的。假设堆里已经有
12，新来的
v = 12 且
12 > 堆顶 8，直接替换会把堆顶换成 12 —— 堆里出现两个 12。
seen 就是用来拦这种「值已在堆里」的情况。
三、动画怎么看
动画用主例（18 个元素、
k = 10、不去重口径），20 帧：
- 输入行：三态 —— 绿底 = 已经进过堆、橙框 = 当前正在判断、灰底 = 被丢掉的；
- 堆行：10 格的层序数组。金底那格（下标 0）是堆顶，也就是「当前第 10 大」；橙框是本次 sift 走过的路径；
- 底部一行：当前堆顶值 + 已丢弃个数；
- 答案条：扫完才亮，给出「第 10 大 = 16」。
值得盯的帧是第 12 个元素（
27）：
27 > 堆顶 8，挤掉 8 之后向下调整到下标 2。你能直接看到「堆里始终是到目前为止最大的 10 个值」这件事在每一帧上都成立。
第二个动画是
同一组数据、去重口径：输入行里重复的
45、
12、
33 全变成灰色（值已在堆里，直接丢弃），最后答案条写着「第 10 大（去重）= 8」。两个动画并排看，口径的差别一目了然。
四、完整推演表
主例
k = 10，前 10 个元素先把堆填满，之后才开始淘汰：
最终堆里是
45, 45, 45, 41, 33, 33, 27, 23, 19, 16（共 10 个），堆顶
16 = 第 10 大。全程只有 2 个元素被
O(1) 丢掉、6 次堆调整 —— 如果数组长到 10 万个元素，绝大部分元素都会在「和堆顶比一下」这一步被丢掉，根本进不了堆。
五、进阶：三种解法的取舍
为什么堆是这题的标准答案：
k = 10 是常数，
O(n log 10) 就是
O(n)，但常数极小，而且
不需要把整个数组装进内存 —— 数据是流式到来的也能做（读一个判一个，堆只留 10 个）。排序做不到这一点，快速选择也做不到（它要随机访问整个数组）。
快速选择（
LC 215 那篇详述）平均
O(n) 更优，但有两个代价：最坏
O(n^2)（对手构造数据可以卡），而且
原地分区会打乱输入顺序。如果面试官追问「能不能 O(n)」，先答堆，再补快速选择作为进阶，是标准的答法。
去重口径的另一个实现：先
set(nums) 去重（
O(n) 空间），再跑同一套堆。代码更短，但多一份
O(n) 空间 —— 流式场景下不可行（你不知道后面还会来什么值，必须一直记着见过的所有值）。动画里用的是流式版本：
seen 只记
堆里的值，被顶出去的值就忘掉，空间
O(k)。
六、Java 版
import java.util.PriorityQueue;
public class KthLargest {
// 找第 k 大。dedupe = true 表示去重口径（distinct 值里第 k 大）
public static Integer kthLargest(int[] nums, int k, boolean dedupe) {
if (nums == null) {
throw new IllegalArgumentException("nums 不能为 null");
}
if (k <= 0) {
throw new IllegalArgumentException("k 必须是正整数，收到 " + k);
}
if (nums.length < k) {
throw new IllegalArgumentException(
"数组长度 " + nums.length + " 小于 k=" + k);
}
// 最小堆，堆顶 = 当前第 k 大
PriorityQueue<Integer> heap = new PriorityQueue<>(k);
Set<Integer> inHeap = new HashSet<>(); // 去重口径用
for (int v : nums) {
if (dedupe && inHeap.contains(v)) {
continue; // 值已在堆里，重复值只算一次
}
if (heap.size() < k) {
heap.offer(v);
inHeap.add(v);
} else if (v > heap.peek()) {
if (dedupe) {
inHeap.remove(heap.peek());
}
heap.poll();
heap.offer(v);
inHeap.add(v);
}
// else: v <= 堆顶，丢掉
}
if (heap.size() < k) {
// 只有去重口径会走到这里：不同值不够 k 个
throw new IllegalArgumentException(
"不同值不足 " + k + " 个，无法求第 " + k + " 大");
}
return heap.peek();
}
}
注意返回类型用
Integer 而不是
int：
无解时要能返回 null。用
int 就得抛异常或者约定一个魔法值（比如
Integer.MIN_VALUE），两者都不如
null 干净。这也是「异常处理」的一部分 ——
把「不可能的情况」设计进返回类型，而不是留给调用方猜。
七、边界情况与异常处理
用户特意点了这一项，逐条列：
一条设计原则：
N < k 和「distinct 不足
k 个」是两种不同的失败，前者跟口径无关、后者只在去重口径出现。分开报错，消息里带上具体数字（
"数组长度 3 小于 k=10"），排查时能省十分钟。
八、复杂度
O(n log k) 的来路：
n 个元素，每个最多触发一次入堆 / 替换，每次堆操作
O(log k)；每个元素最多进堆一次、出堆一次，所以总操作数有常数上界。
k = 10 时
log k ≈ 3.3，实际比排序快一个量级以上。
九、常见坑
9.1 没问口径就开写（本题头号坑）
和上一篇螺旋填数一模一样：
题面里没说的约定，先问再写。 这题更隐蔽 —— 官方样例
[3,2,1,5,6,4] 找第 2 大，两种口径答案都是
5（因为 6 和 5 都不重复），
官方样例根本区分不出口径。必须自己造带重复的用例（比如本篇主例 16 vs 8）。
9.2 用最大堆装全部元素
PriorityQueue 默认就是最小堆，但很多人图省事把所有元素塞进去再
poll() k 次 —— 那是
O(n log n) 时间 +
O(n) 空间，退化成排序。
堆的大小必须限制在 k，这是这题用堆的全部意义。
9.3 去重口径只判「大于堆顶」
漏了「值已在堆里」这一路，会把堆顶换成两个相同的值（详见第二节）。测法：构造
[9, 9, 8] 找去重后第 2 大 —— 正确是
8，错误的实现会给出
9。
9.4 N < k 时返回第 N 大或 0
静默降级比崩溃更危险：调用方拿着「第 10 大」的名次去做业务判断，实际拿到的是最小值。
要么抛异常，要么返回 null 让调用方显式处理。
9.5 忘了 k 可能大于 distinct 数
只有去重口径会踩：
[5,5,5] 找第 2 大，不去重答案是 5，去重口径无解。分支里少写一个
heap.size() < k 的兜底判断，就会把堆顶（5）当答案返回。
9.6 排序法遇上 NaN
Arrays.sort /
sorted 遇到
NaN 时，
NaN 会被排到某一端且比较结果全 false，答案静默错误。
入参校验阶段就拦掉非有限值，别指望排序帮你。
十、面试怎么答
- 先问口径："重复元素算一次还是算多次？两种答案可能差很多。" —— 这句话直接把你和"听完就写"的人分开。
- 给出标准解："维护一个 size-k 的最小堆，堆顶就是当前第 k 大；比堆顶小的 O(1) 丢掉，比堆顶大的挤掉堆顶再向下调整。
O(n log k) 时间、O(k) 空间。"
- 说明为什么不用排序："
k 远小于 n 时堆更快，而且支持流式输入 —— 不需要把整个数组装进内存。"
- 接住 O(n) 的追问："快速选择平均
O(n)，但最坏 O(n^2) 且会破坏输入顺序；如果要保证最坏界，可以用 BFPRT（中位数的中位数），代价是常数巨大，工程上一般不划算。"
- 主动讲异常："
N < k 要抛异常；去重口径还要额外判 distinct 值够不够 k 个，不够就是无解，返回 null。"
- 报变体：LC 215（本题的标准版）、LC 347 前 K 个高频元素（堆 + 哈希）、数据流中位数（双堆）、以及「第 K 大」在数据库里就是
ORDER BY ... LIMIT k（有索引时是 O(k log n)）。
结语
这题是「口径比算法值钱」的又一例：
算法部分人人会写（size-k 最小堆，O(n log k)、O(k) 空间、支持流式），真正的分水岭在开口第一句 —— 去重还是不去重，答案能差一倍（16 vs 8），而且官方样例
[3,2,1,5,6,4] 两种口径都返回 5，根本测不出来。第二道分水岭是异常处理：
N < k、
k <= 0、去重后 distinct 不足、
null 入参、
NaN —— 五种失败模式各有各的正确行为，静默降级比崩溃危险得多。和上一篇
螺旋填数 一样：
先对齐口径，再谈复杂度。