企业官网建设流程全解析

刷题这东西，总有几道题会隔三差五地跟你重逢。Day33，我又撞上了LeetCode 215——数组中的第K个最大元素。实话讲，这道题我在电话面里被问过，在模拟面试里看别人写过，还在某次 code review 里看到同事把线上的“Top K”需求直接 sort 了一把。题面一句话的事：给定整数数组 nums 和整数 k，返回数组中第 k 个最大的元素。

但这句话背后至少藏了三套思路：排序、快速选择、堆。三种解法对应三种复杂度模型，也对应三种不同的应用场景。面试官爱问这道题，恰恰是因为它能快速分辨一个人是背过答案，还是真理解算法本身。

这篇东西写给刚开始刷题的朋友，也写给把答案背下来却还没想明白“为什么”的人。我会把三种解法完整过一遍，补上复杂度推导，再聊一个很多人踩过的重复元素坑，最后说说这道题在工程里的真实用法。放心，不绕弯子，全是能直接拿去用的东西。

1. 题面里藏着的两个关键点：语义与数据规模

1.1 “第K大”不等于“去重后的第K大”

先解决最容易踩的语义坑。题目说的是“返回数组中第 k 个最大的元素”，这里默认的是：排序之后，从大到小数第 k 个位置上的值。它不要求元素唯一，所以重复值每一个都算数。

举个例子。nums = [3, 2, 1, 5, 5, 4]，k = 2。排序后是 [1, 2, 3, 4, 5, 5]，从大到小数第二个是 5，所以答案是 5。如果误把题目理解成去重后的第 2 大，那答案就变成 4 了，直接错。

这个细节在面试里经常被用来做“试探性提问”。你如果一上来就写nums[nums.length - k]，面试官会紧跟着问一句：“那如果我要的是去重之后的第 K 大呢？”这不是刁难，而是想看你会不会主动意识到两个问题的处理差异。去重版本需要用哈希表或者排序后跳过相邻重复元素，复杂度模型完全不一样。

1.2 看一下约束再选策略

刷题第一件事永远是看数据范围。LeetCode 215 的约束是：1 ≤ k ≤ nums.length ≤ 10^5，nums[i] 在 -10^4 到 10^4 之间。这个范围意味着最暴力的思路——直接排序——其实是能过的，毕竟 10^5 个元素的排序在现代机器上就是毫秒级。

但“能过”和“答得好”是两回事。面试官要的不是一个能 AC 的提交，而是你能不能在 N 达到百万、千万甚至更大时，依然给出一个可扩展的方案。这也是这道题存在的意义：它把一个“看似简单”的问题，拆成了一条鄙视链——排序法、堆法、快速选择法，每个层级都能说明你对复杂度和场景的理解深浅。

我把三种主流解法放在一起先看个全貌，后面逐个展开。

这张表的含金量很高。面试时你能报出这张表，基本就把这道题的主干知识讲完了，剩下的都是细节。

2. 排序法：能过测试，但赢不了面试

2.1 三行代码的“满意解”

先看最直白的写法。Java 里用Arrays.sort，Python 里用内置sorted，本质一样：

class Solution { public int findKthLargest(int[] nums, int k) { Arrays.sort(nums); return nums[nums.length - k]; } }

逻辑一句话：升序排序后，第 k 大的元素在正数下标nums.length - k的位置上。别把这个小写没写你页面：你只需要知道一个结论，升序数组里，从右往左数第 k 个元素就是第 k 大。

这道题的测试用例用排序法能直接过，而且提交时间通常很好看。不少初学者刷到这就点“题解”了，但我的建议是：排序法只适合当开场白，别把它当最终答案。

2.2 复杂度账：N log N 到底贵在哪

排序的时间复杂度是 O(N log N)。当 N = 10^5 时，N log N 大概是 170 万次比较操作，确实不算什么。但如果 N 涨到 10^7、10^8，这个量级就开始肉痛了。更重要的是，排序做了大量“多余”工作——它把整个数组排好了，可你只关心第 k 个位置上的值。

打个比方：你参加一场考试，想知道自己是第几名，排序法是让所有人按分数重排一遍，然后看第 k 个人是谁；更聪明的做法是每次只淘汰一批明显不如你的人，直到确定自己的位置。后者不用处理所有名次信息，自然是更优解。

还要注意一个细节：Arrays.sort是原地排序，意思是你的nums数组会被修改。如果业务代码里数组还要继续用，你就得先拷贝一份，空间和时间都会额外增加。这点在刷题时没人管，但工程里经常被忽略。

2.3 排序法的正确打开方式

那排序法是不是就一无是处？也不是。它有几种很合理的适用场景：

• 数组长度很小（比如几百），排序法的常数优势让复杂度的差别变得无所谓；
• 你只需要一次性查询，且不关心原数组是否被改动；
• 作为面试答题的“第一层”，先给一个能跑的版本，再自然过渡到更优方案。

我习惯这么面试：先写排序法，然后主动说“这个解法的时间复杂度是 O(N log N)，但如果面试官希望更快，我可以调整到平均 O(N)”。这套递进在面试官眼里是加分的，因为它说明你不只会背题，还有自己的复杂度判断能力。

真正的问题来了：能不能做到比 O(N log N) 更快？答案是可以，就看下一章。

3. 快速选择：每次砍掉一半，平均 O(N)

3.1 核心是 partition，不是排序

快速选择（Quick Select）的思路源自快速排序里的 partition 操作。partition 干的事是：选一个基准值 pivot，把数组划分成“小于 pivot”和“大于 pivot”两段，然后返回 pivot 最终所在的位置。

快排会递归地把左右两段都排好，但快速选择只需要回答一个问题：目标下标在左边的区间，还是右边的区间？每次划分后，答案只可能存在于一边，所以另一边的数据可以直接无视。这就是它能从 O(N log N) 降到 O(N) 的根本原因。

把原始数组按升序理解，第 k 大的元素在排序后数组的下标是n - k。我们把这个值叫targetIndex。每次 partition 返回的pivotIndex，如果等于targetIndex，那 pivot 就是答案；如果小于它，说明答案在右侧；如果大于它，说明答案在左侧。于是循环地把区间缩小，直到找到为止。

3.2 一个具体的推演过程

拿个具体例子走一遍。nums = [3, 2, 1, 5, 6, 4]，k = 2，那么 n = 6，targetIndex = 4。

第一轮 partition 选 pivot = 4（刚好数组最右边那个）。把小于 4 的换到前面，大于 4 的留在后面，同时把 4 放到它该在的位置，得到 [3, 2, 1, 4, 6, 5]，pivot 的下标是 3。因为 3 < 4，说明答案不可能在下标 3 左边，我们把搜索区间缩到 [4, 5]，也就是子数组 [6, 5]。

第二轮在这个子数组上 partition，随机选到 pivot = 6。交换后 6 到最右边，5 被换到左边，得到 [3, 2, 1, 4, 5, 6]，pivot 的下标是 5。因为 5 > 4，说明答案在左侧，区间缩到 [4, 4]。

第三轮区间只剩一个元素 5，partition 返回下标 4，正好等于 targetIndex，答案就是 5。

整个过程只做了三次 partition，处理的数组长度依次是 6、2、1，加起来不到两倍的数组长度，因此平均 O(N) 不是玄学，是一条可以手推的等比数列。

3.3 随机 pivot 是必需品

快速选择不稳定的唯一来源是 pivot 选得差。如果数组本来就有序，而你又每次都选最右边那个元素当 pivot，那每次 partition 都只会消掉一个元素，复杂度退化成 O(N²)。这是“运气差”和“数据刚好克你”的双重作用。

解法里必须有随机化。代码里我用Math.random()从当前区间随机选一个下标，保证遇到有序数组、逆序数组这类刁钻输入时，不至于每次都踩到最差 pivot。笔试时可能无所谓，但工程里如果线上数据恰好有序，固定选端点的写法可以直接把服务拖垮。

这段是完整的快速选择实现，迭代版本，空间 O(1)：

class Solution { private int[] nums; public int findKthLargest(int[] nums, int k) { this.nums = nums; int n = nums.length; int targetIndex = n - k; int left = 0; int right = n - 1; while (left <= right) { int pivotIndex = partition(left, right); if (pivotIndex == targetIndex) { return nums[pivotIndex]; } else if (pivotIndex < targetIndex) { left = pivotIndex + 1; } else { right = pivotIndex - 1; } } return -1; } private int partition(int left, int right) { int randomIndex = left + (int) (Math.random() * (right - left + 1)); int pivot = nums[randomIndex]; swap(randomIndex, right); int storeIndex = left; for (int i = left; i < right; i++) { if (nums[i] < pivot) { swap(i, storeIndex); storeIndex++; } } swap(storeIndex, right); return storeIndex; } private void swap(int i, int j) { int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; } }

这个版本可以直接提交。代码里有几个值得注意的点：Math.random()虽然比ThreadLocalRandom慢一点，但胜在零依赖、好理解；storeIndex是经典的“读指针”和“写指针”分化的写法；随机下标要算到right - left + 1这个长度上，别写成固定right。

3.4 要不要上严格 O(N) 的算法

面试时如果面试官继续追问“万一随机化还是遇到最坏情况呢”，你可以提一个名字：BFPRT 算法，也叫 Median of Medians。它的思路是先把数组每五个元素一组，找到每组的中位数，再递归找这些中位数的中位数作为 pivot，从而保证每次 partition 至少淘汰固定比例的数据，把整体复杂度严格控制在 O(N)。

但工程里几乎没人写 BFPRT。原因是常数因子太大了：每五个一组的预处理、求中位数的递归、各种数组拷贝，让它在实际运行中的性能甚至可能不如一个随机化快选。BFPRT 更多是理论意义，属于“我知道它存在、能说出原理、但不会在生产代码里写它”的类型。能答到这里，面试官的预期已经拉满了。

4. 堆解法：另一种复杂度模型，另一种适用场景

4.1 小根堆为什么能求出第K大

第一次看到“求第 K 大却用最小堆”的人都会愣一下，直觉是“求最大应该用最大堆”。但这道题恰巧是小根堆更合适。

思路是这样的：维护一个最多只有 k 个元素的小根堆，堆顶永远是堆里最小的那个元素。每遍历一个新数，如果当前堆没满，直接入堆；如果堆满了，并且新数比堆顶更大，那就弹出堆顶、把新数放进去。这等于堆里始终保存着“到目前为止最大的 k 个数”，而其中最小的那个，恰好就是第 k 大。

用代码看更直观：

class Solution { public int findKthLargest(int[] nums, int k) { PriorityQueue<Integer> minHeap = new PriorityQueue<>(k); for (int num : nums) { if (minHeap.size() < k) { minHeap.offer(num); } else if (num > minHeap.peek()) { minHeap.poll(); minHeap.offer(num); } } return minHeap.peek(); } }

跑一遍 nums = [3, 2, 1, 5, 6, 4]，k = 2。先放 3、2，堆变成 [2, 3]；1 比堆顶 2 小，不换；5 比堆顶 2 大，弹出 2 放入 5，堆变成 [3, 5]；6 比堆顶 3 大，弹出 3 放入 6，堆变成 [5, 6]；4 比堆顶 5 小，不换。最后堆顶是 5，正确。

4.2 小根堆与大根堆的对比

有人写堆解法时喜欢用大根堆：把所有元素丢进大根堆，然后做 k-1 次弹出，堆顶就是答案。大根堆的思路完全对，但有两个不划算的地方：空间上要装下全部 N 个元素，是 O(N)；时间上每次入堆 O(log N)，全部入堆就是 O(N log N)，比小根堆的 O(N log K) 差一档。

这个表格值得截图保存。我见过不少同学在面试里写出大根堆版本，面试官一般不会说错，但会追问“空间能压到 O(K) 吗”，本质就是考察这个对比。

Java 里PriorityQueue默认是小根堆，所以小根堆不需要传任何参数；大根堆需要传Comparator.reverseOrder()。还有个细节：new PriorityQueue<>(k)里的 k 是初始容量，不是“最大容量”，堆满后它会自动扩容。所以代码里必须靠size()判断来手动限制大小，别指望构造参数替你固定住。

4.3 选堆还是选快速选择

如果你手头的场景是“一次性给出完整数组，只查一次”，快速选择是更优解，因为平均 O(N) 且空间 O(1)。但如果数据是持续到来的，比如一个几百路并发写入的日志系统，你永远不知道下一秒会不会来一个更大的值，快速选择就只能重新跑一遍，而堆方案是增量式的——来一个处理一个，始终维持 O(log K) 的单次成本。

这也是为什么很多后台系统的实时排行榜模块底层是一个固定大小的堆，而不是每隔几秒做一次全量排序。堆的结构决定它天然适合“流式更新”，这是快速选择做不到的。

再来一个量级上的感知：N=10^6，K=100，堆的时间大约是 10^6 * log2(100) ≈ 700万次堆操作；排序是 10^6 * log2(10^6) ≈ 2000万次比较。堆不一定碾压排序，但当 K 远小于 N 时，堆的常数和内存占用都更可控，尤其 K 小得离谱时优势会放大。

5. 重复元素专杀：三路 partition 与退化防御

5.1 同一个数字刷满数组会发生什么

前面写的快速选择其实还有一个隐藏的天坑：大量重复元素。考虑一个极端用例，数组里全是同一个值，比如 10^5 个 7，k = 2。基础版 partition 会选一个 7 当 pivot，然后遍历数组时发现所有元素都不小于 7，于是一个都没换，最后把 pivot 换到storeIndex也就是区间开头的位置。结果每次 partition 只处理掉一个元素，退化成 O(N²)。

LeetCode 的测试用例里包含大量重复值的场景。我在本地用这个用例跑过基础版快选，耗时惨不忍睹。这就是为什么实际刷题时，很多答案会推荐用“三路 partition”来替代基础版本。

5.2 荷兰国旗 partition 的写法

三路 partition 的思想来自荷兰国旗问题：将数组分成三块——小于 pivot、等于 pivot、大于 pivot。这样一大片等于 pivot 的元素在第一次 partition 后就能全部归位，如果目标值正好落在这片区域里，直接返回，不需要再递归。具体实现：

private int[] partition3(int left, int right) { int pivot = nums[left + (int) (Math.random() * (right - left + 1))]; int lt = left; int i = left; int gt = right; while (i <= gt) { if (nums[i] < pivot) { swap(i, lt); lt++; i++; } else if (nums[i] > pivot) { swap(i, gt); gt--; } else { i++; } } return new int[]{lt, gt}; // 等于 pivot 的区域是 [lt, gt] }

主循环也要跟着改。不再只比较一下pivotIndex和targetIndex是否相等，而是看targetIndex落在三区中的哪一区：

int[] range = partition3(left, right); if (targetIndex < range[0]) { right = range[0] - 1; } else if (targetIndex > range[1]) { left = range[1] + 1; } else { return nums[targetIndex]; }

这段代码处理“全是同一个数”的用例时非常漂亮：第一次 partition 就把整个数组划到等于区域，targetIndex必然落在区域内，直接返回。等于区域越大，节省的时间越多。你可以把三路 partition 当成快选在生产环境中的默认形态。

5.3 实测感受与实际提醒

我在本地对比过两个版本，随机数组时两者表现接近，但以下两种情况三路版优势非常明显：一是数组里存在大量重复值；二是数组有序或逆序的“结构化”数据。后者靠随机 pivot 能化解一部分，但重复值的问题只能靠三路 partition 根治。

还有一个小提醒：三路 partition 返回的是一个长度为 2 的数组，代表等于 pivot 的范围。面试里单独写这个小函数，能体现出你对快排底层的理解已经不是背代码的层次了。配合之前 BFPRT 的讲解，这一整套快速选择相关的问题基本就问到顶了。

如果你用 Java 写了三路版但提交超时，先别急着怀疑算法。检查一下partition3里的Math.random()调用次数，如果构造了大量小数组，随机数生成的开销会被放大。这时可以把数组长度和 targetIndex 的关系单独处理，比如当剩余区间小于某个阈值时直接排序返回，工程上这叫“插入排序优化递归基”，面试时提出来也是亮点。

6. 从215题延伸出的Top K工程视野

6.1 数据流里的实时第K大

LeetCode 有一道题叫“数据流中的第 K 大元素”，原题编号 703，核心就是用一个固定大小的小根堆持续维护 Top K。你只要把 215 题的堆版本稍微封装一下，加一个add()方法，就是 703 题的完整解法。

class KthLargest { private PriorityQueue<Integer> heap; private int k; public KthLargest(int k, int[] nums) { this.k = k; this.heap = new PriorityQueue<>(k); for (int num : nums) { add(num); } } public int add(int val) { if (heap.size() < k) { heap.offer(val); } else if (val > heap.peek()) { heap.poll(); heap.offer(val); } return heap.peek(); } }

这道题在真实业务里的投影是“实时热度榜”：短视频热度、直播间在线人数、搜索热词，都是源源不断的数据流，你不能把历史数据全存下来再一秒钟排序一次。小根堆方案可以做到每次新数据到达时只用 O(log K) 完成更新，K 通常取 10 或 100，成本完全可以接受。

6.2 海量数据内存放不下时的应对

如果数据量大到连单机内存都装不下，比如 TB 级别的日志，堆方案的 O(K) 空间优势就变成了决定性因素。因为你可以逐行读文件，把每一行“喂”给一个固定大小的堆，全程内存占用只有 O(K)，跟数据总量无关。

这是排序法在工程上的致命伤：Arrays.sort需要把整个数组放进内存，海量数据场景根本走不通。所以我在某后台服务里做过一个 Top 错误码统计模块，就是拿一个 100 大小的小根堆，配合哈希表先计数，再逐条喂给堆。代码量不大，却能稳定处理每天几十亿条上报。

还有一种常见方案是“分桶归并”：把海量数据按哈希分到多个小文件里，分别求每个文件的 Top K，最后再对所有 Top K 做一次归并排序。这种方式适合分布式环境，每台机器只处理自己那部分数据，最后汇总。它和“最小堆”并不冲突，归并阶段用的还是堆。

6.3 变体题与我的刷题体会

215 题的变体一大堆，但思路是复用的：

• 求第 K 小：等价于求第 N-K 大，直接套；
• 前 K 个高频元素：先用哈希表统计频率，再对频率做 Top K；
• 数组中最接近原点的 K 个点：把距离算出来，变成第 K 大/小问题；
• 数据流中位数：两个堆，一个大根堆一个小根堆，是 215 题堆思路的进阶版。

我自己刷这道题最大的收获，不是记住了快速选择的代码，而是建立了一种“复杂度模型”的直觉：排序是万金油，但很多问题根本不需要全序；堆适合增量，快选适合一次性；当你发现一个题可以用两种复杂度模型解时，一定要搞清楚场景，再选那套合适的。

如果只让我留一条建议给读者，那就是：三种解法都亲手写一遍，然后不看题解，在纸上把快速选择随机化后的复杂度推导写出来。这道题一旦吃透，Top K 这个家族对你来说就算彻底通关了。