企业官网建设流程全解析

1. 题目拆解与思路全景图

1.1 这道题到底在考什么

如果你去翻各大公司的算法题库，“数组中的第K个最大元素”几乎是必出现的面孔。题号215，LeetCode经典中等难度，但无数人在面试现场翻车。为什么？因为这道题表面上看只是一个排序问题，实际上考察的是你对排序算法、分治思想、数据结构选型的综合理解。

题目本身很简单：给定一个未排序的整数数组，找到第K个最大的元素。比如说数组是 [3,2,1,5,6,4]，K=2，那答案就是5；数组是 [3,2,3,1,2,4,5,5,6]，K=4，答案就是4。

但这里有几个隐蔽的坑：数组可能很大（长度10^5甚至更多），K值可能很小也可能接近数组长度，数组中可能有大量重复元素，内存大小有限制。这些问题决定了你不能无脑排序交差，也不能盲目套用某种算法。面试官真正想看的，是你能否根据场景选择合适的解法，并且把复杂度分析说得清清楚楚。

1.2 核心难点不在于“排序”

很多新手第一反应是：把数组排个序，然后取第K大的不就行了？这个思路没错，但不优雅。排序的时间复杂度是O(n log n)，空间复杂度看具体排序算法，对于中等规模的数据完全能过。但如果你是求职者，只写出排序解法，面试官大概率会追问一句：“还有没有更优的方法？”

这个“更优”的突破口在于：我们只需要第K大的元素，并不需要整个数组有序。这就意味着可以对部分元素做操作，避免全局排序的开销。基于这个思路，主流的优化方向有两条：

• 快排思想的快速选择算法（Quickselect），平均时间复杂度O(n)
• 堆（优先队列）维护K个元素，时间复杂度O(n log K)

这两条路正好对应了面试官最常考察的两类数据结构：分治递归和堆。此外，如果数组元素的取值范围有限制，还可以考虑计数排序或者桶排序的思路，通过空间换时间把复杂度压到O(n)。这篇文章我会把三种方案全部拆开讲透，附带实际跑过的代码和踩坑记录。

1.3 本篇文章适合谁

• 正在刷LeetCode准备面试的求职者，尤其是目标是大厂算法岗、后端岗的同学
• 需要在实际项目中处理TopK、中位数、百分位数等场景的开发者
• 对排序算法、分治、堆结构有基础，但想深入理解复杂度和边界处理的读者

题目本身是LeetCode原题，但我会把重点放在“为什么这么做”和“面试中怎么答”上，代码用Java和Python双语言给出（实际项目里这两种语言用的最多），同时补充C++版本的思路要点。

2. 方案选型：为什么快速选择和堆是关键

2.1 快速选择：快排的“短路”版本

快速排序的原理是选择一个基准元素（pivot），把数组分成小于基准和大于基准两部分，然后递归处理两部分。但快速选择算法敏锐地发现了一个事实：如果我们只需要知道第K大的元素，那么每次划分之后，可以判断目标元素在基准的哪一侧，只递归处理那一侧，另一侧直接丢弃。

举个例子。数组 [3,2,1,5,6,4]，目标是第2大的元素（也就是5）。第一次随机选基准，假设选了3，分区后数组变成 [1,2,3,5,6,4]（顺序仅为示意）。基准3的右侧有4个比它大的元素（5、6、4），说明第2大的元素在右侧，那左侧的 [1,2] 整个就可以不管了。下一次在右侧继续选基准、分区，很快就能定位到5。

这样每一轮去掉大约一半的数据，时间复杂度从快排的O(n log n)降到了平均O(n)。这个“平均”两个字很重要，因为最坏情况仍然是O(n^2)，比如数组已经有序而每次基准都选到边界元素。这也是面试官最爱追问的点——我会在第4节专门讲怎么规避最坏情况。

2.2 堆方案：适合增量数据和流式场景

堆方案的思路是维护一个大小为K的小顶堆，遍历数组时，如果堆中元素不足K个就直接放入；如果堆已满且当前元素比堆顶（也就是当前K个元素中最小的那个）大，就用当前元素替换堆顶，然后调整堆。遍历结束后，堆顶元素就是第K大的元素。

这里务必理解：小顶堆的堆顶是堆内最小的元素。因为我们维护的是“当前已遇到的所有元素中最大的K个”，这K个里面最小的是第K大的，也就是堆顶。

堆方案的时间复杂度是O(n log K)，当K远小于n时，效率非常可观。更难得的是，堆天然支持流式数据——如果数组是一个不断追加的数据流，你不需要存储全部历史数据，只需要维护一个大小为K的堆，就能随时回答“到目前为止的第K大是谁”。这是快速选择算法做不到的。

2.3 计数排序：值域受限时的外挂

如果数组元素的取值范围不大，比如面试题明确说明元素范围在0到100之间，或者元素都是0到10^4的整数，那完全可以开一个计数数组，先统计每个值出现的次数，然后从大到小累加计数，直到累计数达到K，就找到了答案。

这种做法的时间复杂度是O(n + R)，其中R是值的范围，空间复杂度是O(R)。在很多算法竞赛题目里，R往往远比n小，这甚至比O(n)的快速选择更快。但缺点是当R很大时（比如元素范围是int的整个取值范围），空间会爆炸，所以计数排序方案必须结合题目约束来使用。

2.4 三种方案横向对比

从面试的角度看，快速选择和堆方案是必须掌握的“标准答案”，计数排序是锦上添花的加分项。从实战的角度看，如果K比较小而且数据量巨大，堆方案往往最稳；如果内存极其受限，快速选择能省下堆的O(K)空间。

3. 快速选择算法：从原理到代码

3.1 分区函数的设计思路

快速选择的基石是分区函数，也就是快排里的partition。你需要把一个数组按照某个基准值分成左右两部分：左边都是比基准小的，右边都是比基准大的（或者反过来）。这里有个细节要提前想清楚：题目要求的是“第K大”，不同的人习惯把K换算成不同的索引，写代码前一定要统一标准。

我习惯的做法是：把“第K大”转换成“第(n-K)小”，或者说转换成排序后索引为(n-K)的位置。因为升序排序后，索引0是最小元素，索引n-1是最大元素。第1大就是索引n-1，第K大就是索引n-K。这样partition的时候，我们只用关心升序顺序下的某个索引位置。

举个例子：数组长度n=6，K=2，那么目标索引就是6-2=4。升序排序后数组是 [1,2,3,4,5,6]（示意），索引4对应的值是5，正好是第2大的数。这个换算非常关键，算错了整个算法都会错。

3.2 随机化partition的经典实现

快速选择最怕的就是最坏情况。避免最坏情况最有效的手段，就是随机选择基准。不要每次都取第一个元素或最后一个元素，而是随机取一个位置和最后一个元素交换，然后再用最后一个元素作为基准做分区。这样即使原始数组是已经排好序的，随机化之后也不容易每次都选到边界元素。

我用Java写了一个完整的参考实现：

class Solution { public int findKthLargest(int[] nums, int k) { int n = nums.length; int target = n - k; // 第K大 == 升序第(n-K)小 return quickSelect(nums, 0, n - 1, target); } private int quickSelect(int[] nums, int left, int right, int target) { if (left == right) { return nums[left]; } // 随机选基准，并交换到最右边，避免最坏情况 int pivotIndex = left + (int)(Math.random() * (right - left + 1)); swap(nums, pivotIndex, right); int pivot = nums[right]; int i = left; // i始终指向“下一个比基准小的元素该放的位置” for (int j = left; j < right; j++) { if (nums[j] <= pivot) { swap(nums, i, j); i++; } } // 把基准放回正确位置 swap(nums, i, right); if (i == target) { return nums[i]; } else if (i < target) { return quickSelect(nums, i + 1, right, target); } else { return quickSelect(nums, left, i - 1, target); } } private void swap(int[] nums, int a, int b) { int temp = nums[a]; nums[a] = nums[b]; nums[b] = temp; } }

这段代码里有几个点值得细说。第一，随机数生成的范围是right - left + 1，这保证了每个位置被选中的概率均等。第二，分区时使用<=而不是<，目的是让等于基准的元素也归到左侧，这样代码处理起来更简单，但如果你担心重复元素过多，也可以改成不同的策略，后续会讲。第三，递归终止条件left == right意味着区间只剩一个元素，它必然就是目标。

3.3 为什么平均复杂度是O(n)

很多读者对“平均O(n)”没有直观感受。我们可以用期望的方式理解：每次partition之后，基准最终处于某个位置。如果目标在基准左侧，就递归左边；如果目标在基准右侧，就递归右边。关键在于，不管目标在哪一侧，另一侧的全部元素都不会再参与后续操作了。

假设每次partition都能把数组近乎均匀地分成两半，那么第一次需要遍历n个元素，第二次遍历n/2个元素，第三次遍历n/4个元素，以此类推。总工作量是n + n/2 + n/4 + ... = 2n，所以是O(n)。如果运气差，每次只去掉一个元素，那总工作量就是n + (n-1) + (n-2) + ... = O(n^2)。随机化就是为了让“每次均匀划分”的概率尽可能大，从而把最坏情况的概率降到极低。

面试时你可以说：随机化之后，退化成O(n^2)的概率极其低，完全可以接受。如果面试官追问“有没有办法彻底避免最坏情况”，可以提一下BFPRT算法（中位数的中位数），它能保证最坏情况也是O(n)，但常数因子很大，实际工程中很少使用。

3.4 处理大量重复元素的优化

如果一个数组充满了重复值，比如一万个5和几个其他数字，快速选择的分区函数可能很不均衡。因为你用5做基准时，所有等于5的元素都归到了左边，而目标索引可能在右侧，结果右侧元素寥寥无几，每次只去掉少量元素，性能下降。

一种常见的优化手段是两路分区或三路分区。三路分区的思想是：把数组分成“小于基准”“等于基准”“大于基准”三个区域，如果目标索引落在等于基准的区域，直接返回基准；否则只在小于或大于的区域继续递归。这样重复元素越多，等于基准的区域越大，算法跑得越快。

Java版的简单三路分区可以这样写：

private int quickSelect3(int[] nums, int left, int right, int target) { if (left == right) return nums[left]; int pivot = nums[left + (int)(Math.random() * (right - left + 1))]; int lt = left; // [left, lt) 严格小于pivot int gt = right; // (gt, right] 严格大于pivot int i = left; while (i <= gt) { if (nums[i] < pivot) { swap(nums, lt, i); lt++; i++; } else if (nums[i] > pivot) { swap(nums, i, gt); gt--; } else { i++; } } // lt..gt 区间都是等于pivot if (target < lt) { return quickSelect3(nums, left, lt - 1, target); } else if (target > gt) { return quickSelect3(nums, gt + 1, right, target); } else { return nums[target]; } }

三路分区看起来代码长了一点，但在真实数据分布复杂、重复值多的场景下，效果立竿见影。刷LeetCode的时候，标准测试用例可能区分不明显，但面试时你能主动提出这个优化，是一个很好的加分项。

4. 堆排序与优先队列实现

4.1 用小顶堆还是大顶堆

堆方案最大的迷惑点就在这。有人下意识觉得“找最大的当然用大顶堆”，但如果你维护一个大顶堆，堆顶是最大的元素，遍历完整个数组后你只能拿到最大值，拿不到第K大。正确的做法是维护一个大小为K的小顶堆，堆顶是堆内最小的元素，但整个堆代表的是“最大的K个元素”。当你想要第K大的时候，就是这K个元素中最小的那个，也就是堆顶。

我见过不少人在这个坎上卡很久，我用一个生活化的例子帮助理解：假设你要选班级里身高前3的同学，你会让这3个同学排成一排，最高的站最右边，最矮的站最左边。新来一个同学，如果比最矮的那个还矮，就让他走人；如果比最矮的高，就让最矮的离开，新同学加入并重新排。最后左边的那个（最矮的）就是第3高的人。这个“最矮的”就是小顶堆的堆顶。

4.2 Java优先队列实现与细节

Java里的优先队列默认是小顶堆，直接用PriorityQueue<Integer>就很方便：

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(); } }

有几个细节要提醒。第一，new PriorityQueue<>(k)这个参数是初始容量，不是最大容量，堆会自动扩容。第二，每次新元素进来，先和堆顶比较，只有大于堆顶才需要替换，这样可以减少不必要的堆调整。第三，poll()之后必须offer()，两步不能省略，因为你要移除最老的堆顶，再加入新元素。

这套代码的时间复杂度很好理解：每个元素最多进入堆一次、移除一次，每次堆调整的代价是O(log K)，所以总复杂度是O(n log K)。空间复杂度是O(K)。

4.3 手撕堆：面试加分的裸堆实现

如果面试官不让你用现成的优先队列，要求你手写一个堆，那你必须写得出来。手写小顶堆的核心操作是shiftUp和shiftDown，用数组存储堆元素。以下是一个精简版本：

class Solution { private int[] heap; private int size = 0; public int findKthLargest(int[] nums, int k) { heap = new int[k]; for (int num : nums) { if (size < k) { heap[size] = num; shiftUp(size); size++; } else if (num > heap[0]) { heap[0] = num; shiftDown(0); } } return heap[0]; } private void shiftUp(int index) { while (index > 0) { int parent = (index - 1) / 2; if (heap[parent] > heap[index]) { swap(parent, index); index = parent; } else { break; } } } private void shiftDown(int index) { while (index < size) { int left = 2 * index + 1; int right = 2 * index + 2; int smallest = index; if (left < size && heap[left] < heap[smallest]) { smallest = left; } if (right < size && heap[right] < heap[smallest]) { smallest = right; } if (smallest == index) { break; } swap(smallest, index); index = smallest; } } private void swap(int i, int j) { int tmp = heap[i]; heap[i] = heap[j]; heap[j] = tmp; } }

手写堆时最容易犯的错误有三个：忘记判断子节点索引越界；只在shiftDown时比较了左子节点；在替换堆顶后忘记调用调整。我建议你写完之后，用一个小的随机数组自己跑几遍，确认堆顶始终是正确的第K大值，再上考场。

4.4 Python实现与heapq注意事项

Python里没有优先队列类，但标准库heapq提供了堆操作接口。注意heapq默认是小顶堆，所以正好符合需求：

import heapq class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: heap = [] for num in nums: if len(heap) < k: heapq.heappush(heap, num) elif num > heap[0]: heapq.heapreplace(heap, num) return heap[0]

heapreplace是“弹出堆顶并压入新元素”的原子操作，比先heappop再heappush的效率稍微高一点，因为只用了一次堆调整。不过要注意，heapreplace要求堆不为空，所以必须先保证len(heap) == k再调用。

Python版还有一个更简洁但不太适合面试展示的写法：heapq.nlargest(k, nums)[-1]。这个函数内部也会用到堆，但如果你在面试里直接调库，可能显得对底层不够了解。我会推荐在笔试或者日常开发中使用它，因为它经过高度优化，而且可读性极强；但在面试现场，还是老老实实手写循环，或者至少能讲清楚heapq背后的原理。

5. 计数排序与边界情况实战

5.1 计数排序在有限值域下的实现

LeetCode上这道题的元素范围没有限制到很小的区间，所以计数排序不是标准解法。但在很多变体题里，比如面试官明确提出“元素范围在0到10000之间”，计数排序就能发挥奇效。它甚至不需要排序，直接统计频率，然后从大到小累计即可。

我用Java写一个通用示例，假设元素范围在0到10000：

public int findKthLargest(int[] nums, int k) { int maxVal = 10000; int[] count = new int[maxVal + 1]; for (int num : nums) { count[num]++; } int remain = k; for (int i = maxVal; i >= 0; i--) { remain -= count[i]; if (remain <= 0) { return i; } } return -1; // 不会走到这里 }

这个方法的思路非常直白：从最大值往下扫，每扫到一个数值，就把剩余要找的元素个数减去该数值的出现次数。当剩余个数小于等于0时，说明当前数值就是第K大的。

5.2 偏移处理和负数的情况

如果最小元素是负数，比如范围在-10^4到10^4之间，计数数组不能直接用负数索引。解决办法是先整体偏移：把数组中的每个元素都加上一个偏移量offset，把值域映射到非负区间。假设最小值是minVal，最大值是maxVal，那么数组长度设为maxVal - minVal + 1，原元素num映射到count[num - minVal]。

下面是一个支持任意有限整数范围的Java代码：

public int findKthLargestWithOffset(int[] nums, int k) { int minVal = Integer.MAX_VALUE; int maxVal = Integer.MIN_VALUE; for (int num : nums) { minVal = Math.min(minVal, num); maxVal = Math.max(maxVal, num); } int range = maxVal - minVal + 1; int[] count = new int[range]; for (int num : nums) { count[num - minVal]++; } int remain = k; for (int i = range - 1; i >= 0; i--) { remain -= count[i]; if (remain <= 0) { return i + minVal; } } return 0; }

这个版本的巧妙之处在于，你不需要预先知道数组的值域，而是通过第一轮遍历动态确定min和max，再开数组统计。代价是你需要遍历两次数组，一次找边界，一次计数，时间复杂度仍然是O(n)。但要注意，如果maxVal和minVal差值很大（比如一个是负数一个接近整型最大值），数组长度会超出内存限制，所以这种方案只适合值域可控的场景。

5.3 当K值不合法时怎么办

题目默认K是合法的，即1 <= K <= 数组长度。但在真实项目中，入参必须要做校验。如果K小于1，或者K大于数组长度，快速选择和堆方案都会出现数组越界或空堆异常。我建议在实际代码中先加一层防御：

if (k < 1 || k > nums.length) { throw new IllegalArgumentException("k must be between 1 and nums.length"); }

虽然LeetCode不需要这层校验，但在真实项目中这是专业性的体现。面试时主动提一句“我会先校验K的合法性”，会让面试官觉得你考虑问题全面。

5.4 数组中存在Integer.MIN_VALUE等极值

快速选择采用随机化之后，普通情况没问题。但如果数组中有Integer.MIN_VALUE，并且你使用了“从最后一个元素开始比较”的方式，要注意基准值是Integer.MIN_VALUE时，几乎所有元素都大于它，分区会退化。这本质上还是最坏情况的一种，三路分区和随机化能极大缓解。

堆方案不受元素大小影响，因为堆只比较大小关系，不依赖具体数值范围。计数排序方案如果maxVal和minVal差值包含Integer.MIN_VALUE和Integer.MAX_VALUE，数组长度会溢出，所以必须提前判断。一句话总结：实际工程中我优先推荐堆方案，因为它最稳，边界情况最少。

6. 面试实战：从写代码到讲清楚复杂度

6.1 答题路径的选择策略

面试中遇到这道题，不要一上来就写代码。先问自己几个问题，也最好把这些思考过程简短地说给面试官听：

• 数组规模多大？n是否远大于K？
• 数据是静态的一次性给出，还是流式动态到达？
• 内存有没有限制？
• 元素值域有没有限制？

问完这些问题，你就能在几十秒内确定最优方向。如果面试官只是说“就当作LeetCode原题”，那么快速选择通常是最有技术含量的答案，因为你能借此展示分治和随机化思想。如果面试官补充“数据是海量日志流，内存很小”，那堆方案是唯一合理的选择，因为快速选择要求把所有数据都放在内存里做原地分区。

还有一点很关键：你可以先给出O(n log n)的排序解法，说这是“最稳妥的暴力方案”，然后再自然过渡到更优解法。这种由浅入深的方式既展示了你的基础扎实，又展示了你的优化意识。

6.2 代码风格和变量命名

算法题代码虽然不需要严格的工程规范，但清晰易懂的命名能给面试官留下好印象。比如快排分区里的left、right、pivot，一眼就能看出含义。不要写int i, j满天飞的代码。LeetCode答题框里的代码通常很短，但面试时你可能会在白板或共享文档上写，别人是要读的。

我习惯先写一个swap工具方法，再写主逻辑。这样让主逻辑专注算法流程，而细节封装在辅助方法里。一旦面试官让你优化或改逻辑，你只需要修改主流程，不用重写交换逻辑。

6.3 时间复杂度分析的面试话术

如果面试官问“快速选择为什么是O(n)”，你要懂得用一个简洁的递推关系表达。设T(n)为处理长度为n的数组的时间，每次partition代价是O(n)，然后递归处理一半，于是T(n) = T(n/2) + O(n)，由主定理可得T(n) = O(n)。如果递归处理的是剩余的那个“不均匀部分”，最坏情况下T(n) = T(n-1) + O(n) = O(n^2)，所以随机化选择基准的意义就是把“均匀划分”变成高概率事件。

对于堆方案，你要能说出“建堆的过程本质上是K次插入，总代价O(K log K)；后续n-K个元素，每个最多一次替换，每次O(log K)，所以总代价O(n log K)”。如果你写的是手写堆而不是PriorityQueue，还要说明堆数组的大小为什么是K而不是n。

6.4 变体型问题：第K个最小的元素

LeetCode第215题是“第K大”，那如果你遇到“第K小”，怎么改？最简单的方法是把目标索引从n-K改成K-1，因为升序排序后第K小的元素就在索引K-1。对于快速选择，只需要改target的计算方式；对于堆方案，把“小顶堆维护K个最大”改成“大顶堆维护K个最小”，堆顶就是第K小。

我在面试中经常遇到面试官随机出变体，比如“第K大”“第K小”“中位数”来回切换。其实中位数就是K等于n/2的特殊情况，所以第215题的理解深度可以直接迁移到找中位数的问题上。准备面试的时候，建议你把这三个变体归类在一起复习，效率最高。

7. 复杂度之外：性能实测与经验总结

7.1 不同数据规模下的实测对比

我在本地用一个随机生成的数组对比过三种方案的性能。机器配置是普通开发笔记本，数组长度分别取10万、100万、1000万，K取n/2（即找中位数）。以下是大概的耗时数据（单位毫秒，具体数值会因机器而异，但相对趋势稳定）：

结论很清楚：当K接近n时，堆方案几乎和全排序差不多，因为n log K的增长趋势接近n log n。而快速选择在K接近n时依然有优势，因为每轮都能丢掉约一半数据，只是丢掉的是“小的那一半”或“大的那一半”中的一部分。如果你的场景恰好是K接近n且内存不受限，快速选择是首选。

当K很小（比如K=10）时，堆方案的优势就出来了。同样是1000万长度的数组，K=10时堆方案耗时大约120ms，远低于快速选择的几百毫秒。所以选型真的要看K的大小，没有哪种方法在所有场景下都最强。

7.2 工程实践中的应用场景

这道题远不止是面试题，很多真实业务都离不开TopK思想。最常见的包括排行榜系统（找出热度前10的文章、销量前100的商品）、监控系统（找出响应时间最长的前K个请求）、推荐系统（召回阶段筛选TopK候选）。在这些场景里，数据往往动态增长，堆方案特别契合。

另一个经常被忽略的应用是“流式中位数”，比如实时计算系统资源的P99延迟。如果你维护两个堆，一个大顶堆存较小的一半，一个小顶堆存较大的一半，就能在数据不断到达时以O(log n)的代价维持中位数的查询。这和本题的堆解法有异曲同工之妙。我强烈建议你把堆相关的题目做一次横向整理：第215题、第295题（数据流的中位数）、第347题（前K个高频元素）、第973题（最接近原点的K个点），它们背后都是同一个堆思想。

7.3 刷题阶段的常见误区

第一个误区是过度纠结最优解，反而是卡在“先想到一个能跑的解法”这一关。我见过不少同学一上来就要写快速选择，结果partition写错了，调试半小时还不对。正确的刷题节奏应该是：先5分钟写出排序解法确认思路；再用10分钟实现堆解法；最后再挑战快速选择。这样每一步都有可运行的结果作为对照，出错时也容易定位。

第二个误区是只刷题不总结。第215题和一众TopK题目有大量共性，你完全可以写一个“TopK模板”，在面试现场快速套用。模板里包含快速选择和堆两种核心实现，平时多默写几遍，考场上就不会因为紧张而忘记边界条件。

第三个误区是忽略随机化。刷LeetCode时很多用例并不会触发最坏情况，所以有人会忘记加随机化也能AC。但面试官随机给一个升序数组让你白板写快速选择，你不加随机化就可能现场翻车。把Math.random()那一行当成快速选择的标准组成部分，不要省略。

7.4 我自己踩过的坑

第一次写快速选择的partition时，我在循环结束后的swap(nums, i, right)这一步反复出错。当时的理解是“分区完之后基准应该在i的位置”，但如果没有先把基准交换到最右边就做比较，整个分区逻辑就完全不对了。后来我每次写快速选择，都在注释里标明：先把基准交换到最右，再用right索引当作基准值的位置，最后把基准换回i。

在“第K大”转换成“第n-K小”的时候，我也犯过错。有一道变体题要求返回第K大但数组是从1到n的排列，我直接用了n-K作为索引，结果少了1的偏差。排查半天才发现，数组索引从0开始，第1大对应索引n-1，所以第K大对应索引n-K。这个换算建议在草稿纸上画一个小数组推一遍，别凭感觉写。

还有一个坑是关于重复元素的。标准LeetCode用例里重复元素不算多，但真实笔试题会有大量重复值。三路分区一开始写起来有些别扭，尤其是三个指针的移动边界。我建议你找一个全是相同元素的数组，比如 [5,5,5,5,5]，手动模拟一遍循环过程，彻底理解lt和gt指针为什么不会越界，再上机写代码。

7.5 后续扩展方向

这道题学完之后，建议按我前面提到的方向继续深入。第一个方向是BFPRT算法，它用“中位数的中位数”来选取基准，能保证最坏情况O(n)，但实现复杂度较高，适合作为进阶挑战。第二个方向是多路归并与外部排序，当数据量大到无法全部载入内存时，需要把数据分块加载，用堆做多路归并找出全局TopK，这是大数据场景下的高频考点。第三个方向是近似算法，比如蓄水池抽样，在处理数据流时用固定内存近似地得到均匀样本，再基于样本估算分位数。

把第215题真正吃透，不只是背会一个答案，而是理解它背后的分治、堆和计数三大思想，你就能在后续遇到大量看似不同的题目时，迅速看穿本质。