第一次在力扣hot100里刷到“数组中的第K个最大元素”这道题时我第一反应和大多数人一样“这不就是排序吗”排个序按下标取一下完事了。直到有次模拟面试面试官追问了一句“如果数组长度有10亿内存只能放100个元素你还怎么排序”我才意识到这道题真正要考察的并不是“会不会排序”而是对Top K问题的理解深度。作为力扣hot100里的常客215题几乎出现在各个阶段的算法面试中从校园招聘到社招都可能碰到原题或变体。它看起来只有一行描述却串起了排序、堆、快速选择、分治这些高频核心算法。无论你是在刷题冲刺面试还是单纯想提升代码功底把这一题吃透性价比都非常高。1. 先别急着排序这题到底在考什么1.1 题目表象与真实考点题目描述很简短给定整数数组nums和整数k返回数组中第k个最大的元素。比如nums [3,2,1,5,6,4]k 2结果就是5。注意这里说的是“第k个最大”不是“第k个最小”。一个常见的理解陷阱是把第2大理解成“第二个出现的较大的数”实际上它就是排序后从后往前数第k个元素。这道题表面上是求一个确定的值本质上是一个“部分排序”问题。它的核心矛盾在于你并不需要把整个数组完整地排好序只需要找到“站在第k个位置上的那个元素”。很多人一开始就Arrays.sort()或者nums.sort()虽然能做对但完全没有利用这道题的特殊性。面试官在考察时最关心的是你能不能从“排序”这个舒适圈里跳出来意识到存在更优的选择型算法。用一个生活中的例子来理解你想知道全班同学里身高第三高的人是谁正常思路是让全班按身高排成一列然后数第三个人。但更高效的做法是手里只记下“当前最高的三个人”遍历一遍所有人每看到一个比手里第三名高的就把他替换进来。这样你不需要让全班同学排队只需要记住3个人的信息就够了。215题考察的就是这种“不需要全排序只要局部信息”的思维。1.2 为什么排序不是最佳答案先给排序一个公平的评价用排序解题代码最简单逻辑最不容易错作为第一版答案完全没毛病。但时间复杂度是O(n log n)空间复杂度是O(1)原地排序或O(n)额外数组。这个复杂度在大多数在线评测系统里都能过因为215题的默认数据范围不算极端。但算法面试不只是“能过样例”就行。面试官会继续追问如果n是10的8次方呢如果数据是流式进入的呢如果内存只够保存很小一部分数据呢这时候全量排序立即崩盘。你需要让算法复杂度与“你需要多少信息”相关而不是与“整个数组有多少信息”相关。这里就引出了分层方案排序方案O(n log n)适合一次全量数据、不追求最优的场景。最小堆方案O(n log k)空间O(k)适合k远小于n的场景也天然支持流式数据。快速选择方案平均O(n)最坏O(n²)适合数组已全部在内存中且可以原地修改的场景。计数排序/桶排序如果数值范围有限可以做到O(n 值域)但适用范围窄。BFPRT中位数的中位数最坏也能O(n)但常数较大工程上很少手写面试时提到即可。理解了这个层次你就知道为什么很多大厂面试爱考这题它不考察你是否背得出某个偏门算法而是考察你在不同的资源约束下能不能选出合适的工具并把手上的工具用对、用好。2. 方案一最小堆维护前K大最稳妥的工业级思路2.1 最小堆的思路与复杂度先说一个直觉上很诱人的方案用一个最大堆把整个数组建堆然后连续弹出k次堆顶就是第k大的元素。这个方案的时间复杂度是O(n k log n)。如果k很小比如1或者2确实非常快。但它的致命缺点是空间复杂度是O(n)因为你必须把整个数组都放进堆里。当数据量达到千万、亿级别时这个空间开销会让人很难受。更优雅的方案是维护一个大小为k的最小堆。思路是这样的遍历数组时始终保持堆里存放的是“当前已见过的所有元素中最大的k个”。怎么维护当堆没满时直接往里放当堆满了如果新元素比堆顶还小说明它连目前第k大都进不去直接跳过如果新元素比堆顶大说明它把原第k大挤掉了于是先用新元素替换堆顶再调整堆结构。为什么最后堆顶就是答案因为堆里永远保存着最大的k个数而最小堆的堆顶是这k个数里最小的那个。这个“最小的那个”正是全局第k大。举个例子假设k3你维护的堆里是[10, 9, 8]堆顶是8。新来一个78比7大说明7连前3都进不去新来一个11比8大于是把8踢掉堆变成[9, 10, 11]堆顶变成9。整个过程结束后堆里就是所有数字里最大的3个而堆顶就是第3大。这个方案的时间复杂度是O(n log k)。因为每个元素最多经历一次入堆和一次出堆每一次堆调整都是O(log k)。空间复杂度是O(k)。和全量排序相比它的优势非常明显不需要一次性持有全部数据可以一条条处理流式数据在k远小于n的场景下时间也接近O(n)。2.2 三种主流语言的代码实现用Java实现最直接。Java的PriorityQueue默认就是最小堆没有任何额外的配置public int findKthLargest(int[] nums, int k) { PriorityQueueInteger heap new PriorityQueue(); for (int num : nums) { if (heap.size() k) { heap.offer(num); } else if (num heap.peek()) { heap.poll(); heap.offer(num); } } return heap.peek(); }这段代码里有两个细节需要注意。第一先判断heap.size() k而不是先无条件offer再poll这样可以减少入堆次数尤其是当数组里大量元素比堆顶还小时直接跳过能省下很多次堆调整。第二heap.peek()拿到的是堆顶元素也就是当前堆里的最小值千万不要把它当作“最大值”用。C里要用到priority_queue默认是大顶堆所以需要指定greaterint让它变成小顶堆int findKthLargest(vectorint nums, int k) { priority_queueint, vectorint, greaterint pq; for (int x : nums) { if (pq.size() k) { pq.push(x); } else if (x pq.top()) { pq.pop(); pq.push(x); } } return pq.top(); }Python的heapq模块默认也是最小堆配合一个简单的列表就能用import heapq def findKthLargest(nums, k): heap [] for num in nums: if len(heap) k: heapq.heappush(heap, num) elif num heap[0]: heapq.heapreplace(heap, num) return heap[0]Python里有个小技巧先用heappush再heappop要调整两次堆而heapreplace是先弹出堆顶再插入新元素底层只做一次堆化流程性能更好。如果用的Python版本支持也可以直接用heapq.nlargest(k, nums)[-1]一句话搞定。但面试手写时还是建议写上面这个循环版本更能展示你对堆操作的理解。2.3 面试追问与变体写完最小堆解法后面试官常见的追问方向就来了。第一个方向是“如果k也很大怎么办”。当k接近n时最小堆的空间也接近O(n)时间复杂度接近O(n log n)此时不如直接用快选或者在特定条件下直接用排序。如果数据量真的到内存放不下的程度那就得聊外部排序、多路归并、分布式Top K这些工程话题了。第二个方向是“如果数组是流式的怎么办”。这正是最小堆方案的高光时刻。它不需要一开始就拿到整个数组可以一个一个处理。实际业务里的“实时排行榜”“热门商品Top K”基本都是这个思路维护一个小堆新数据来了就更新堆堆顶永远是最新的第K名。第三个方向是“如果k等于1或者等于n呢”。k1就是求最大值直接一趟遍历取最大就行不需要堆。kn就是求最小值同理。写代码时如果看到这两个边界值可以直接返回max/min既简单又避免不必要的堆操作。3. 方案二快速选择平均线性时间的核心算法3.1 从快排到快速选择快速选择是快排的变体也是很多面试官心里真正想听到的答案。它的核心思想来自快排的partition分区操作选定一个基准元素pivot经过一次分区后pivot会落到它最终应该在的位置。比如按从小到大分区pivot左边的元素都小于等于它右边的元素都大于等于它。这时候pivot的位置pos就是它在有序数组中的索引。于是我们可以做判断如果pos恰好等于我们想要的目标索引target那pivot本身就是答案如果pos target说明答案在pivot右边只需要继续处理右半部分如果pos target说明答案在左边只要处理左半部分。关键就在这里快排需要递归处理两边而快速选择每次只需要处理一边另一边的元素完全不用管。复杂度为什么是O(n)我们用改进的递推来看。第一轮分区需要扫描整个数组代价是n。如果目标落在半边下一轮只需要处理大约n/2个元素代价n/2。再到下一轮n/4依此类推。总代价是n n/2 n/4 ... ≈ 2n所以平均情况下是线性的。但最坏情况非常尴尬如果每次选到的pivot都是当前区间的最小值或最大值那么每轮只能排除一个元素总代价变成n (n-1) (n-2) ...是O(n²)。为了避免这个退化常规做法是随机选pivot让最坏情况出现的概率变得极低。这也是“快速选择”这个名字里“快速”二字的底气来源。3.2 用具体例子跑一遍分区过程看一个具体的例子更容易理解。假设nums [3,2,1,5,6,4]k 2。先把问题转换一下从小到大排序后是[1,2,3,4,5,6]第2大是5它的索引是n - k 6 - 2 4。所以我们要找到最终有序数组中索引为4的那个元素记target 4。第一轮取区间[0, 5]选择pivot 3。从小到大分区后数组可能变成[2,1,3,5,6,4]此时pivot的索引是2。因为2 4说明答案在右半部分于是下一轮只看[3, 5]区间对应元素是[5,6,4]。第二轮在区间[3, 5]里选pivot 5。分区后右区间变成[4,5,6]pivot的全局索引变成4。此时4 target直接返回5整个过程结束。可以对比一下如果第一轮选到的pivot 6那么一次就发现pos 5 target下一轮只需要看[0,4]区间也很高效。快速选择的时间开销主要取决于pivot选得好不好。用随机化之后连续选到很差的pivot的概率几乎可以忽略不计。3.3 随机化快速选择代码与避坑重点给出一个经典的迭代版本避免递归过深。代码按从小到大分区目标索引是n - kint partition(vectorint nums, int left, int right) { int pivotIndex left rand() % (right - left 1); int pivot nums[pivotIndex]; swap(nums[pivotIndex], nums[right]); int storeIndex left; for (int i left; i right; i) { if (nums[i] pivot) { swap(nums[i], nums[storeIndex]); storeIndex; } } swap(nums[right], nums[storeIndex]); return storeIndex; } int findKthLargest(vectorint nums, int k) { int left 0, right nums.size() - 1; int target nums.size() - k; while (left right) { int pos partition(nums, left, right); if (pos target) return nums[pos]; else if (pos target) left pos 1; else right pos - 1; } return -1; }这种写法比双指针partition更容易理解也更好背。核心思想是维护一个storeIndex凡是比pivot小的元素都交换到左边最后把pivot放到它最终位置。注意这里比较条件是nums[i] pivot所以相同元素会被分到右边。如果你面对全重复数组这个写法仍然可能退化但概率已经很低。如果追求更稳可以改成三路分区把等于pivot的元素单独放中间。这个属于进阶优化面试时能说清楚就更好了。手写快速选择时我踩过最多的坑是“索引搞混”。写代码前一定要先在纸上明确题目要的是第k大我们从小到大分区就找n-k这个索引如果你用从大到小分区就找k-1这个索引。两种方式都有人用没有谁绝对更好但必须一致。另外快速选择会原地修改数组。如果面试官强调“不能修改原数组”你需要先拷贝一份再操作或者改用堆方案。4. 踩过的坑与实测对比4.1 边界条件与特殊用例速查表我整理了一张速查表覆盖了最常见的边界情况。这些情况在力扣原题里基本都合法但企业笔试或面试手写时不一定有保证提前判断一下能避免很多尴尬。场景可能现象处理建议数组为空直接越界或返回错误先判空按题目要求返回默认值k 0或k n逻辑错乱非法输入直接抛异常或返回默认值k 1求最大值一趟扫描即可不需要堆或快选k n求最小值一趟扫描即可数组全部相同快选可能退化或返回任意值堆解法稳快选建议用三路分区数组非常大内存受限堆也需要O(k)空间考虑外部排序/多路归并思路题目不允许修改原数组快选导致原数组顺序变化拷贝一份再操作特别说下全重复数组。如果数组是[5,5,5,5,5]找第2大结果当然还是5。堆方案毫无压力。快选用我上面给的普通partition由于所有元素都和pivot相等storeIndex几乎不动最后返回的可能一直是左端点然后递归右边或左边时仍然处理大量重复元素复杂度可能退化。处理办法是使用三路分区把等于pivot的元素集中到中间或者干脆先做一个if (left right)终止条件。4.2 多语言API与索引换算同样是“排序”不同语言的默认行为差很多。比如JavaScript的Array.sort默认按字符串字典序排序所以[10, 9, 2].sort()得到的是[10, 2, 9]不是数值顺序。你需要写成arr.sort((a, b) a - b)。这也是很多前端同学刷题时第一次踩坑的地方。C的priority_queue默认是大顶堆想用最小堆必须写priority_queueint, vectorint, greaterint。Java的PriorityQueue默认是小顶堆而Python的heapq默认也是小顶堆。如果面试官让你用某种语言手写堆你得提前弄清楚这个默认方向否则求第k大可能变成求第k小。索引换算也是重灾区。题目求第k个最大如果你按从小到大排序理解索引是n - k按从大到小理解索引是k - 1。很多解法在讨论区里用从大到小分区代码里直接if (pos k - 1)看着很简洁但容易让人疑惑。我建议统一用从小到大分区加n - k因为这样和“从小到大排序后取倒数第k个”的心理模型一致出错概率低。关于标准库C选手可以考虑直接用nth_element它能保证某个位置上的元素是最终有序状态下的值但注意它是求第n小。比如求第2大nth_element(nums.begin(), nums.begin() nums.size() - k, nums.end()); return nums[nums.size() - k];这个函数底层通常实现为快速选择但面试手写时如果你直接调库很可能被追问“内部怎么实现的”所以我还是建议先能手写再谈优化。4.3 时间/空间复杂度追问怎么答面试官问复杂度时不只是要一个结论还希望你解释推导。快速选择的平均复杂度推导可以用“每轮处理区间近似减半”来理解但更严谨的表述是T(n) T(n/2) O(n)。如果你是用随机化版本还可以说“随机pivot带来的期望复杂度为O(n)”。堆方案的复杂度推导相对简单。每个元素入堆/出堆各一次每次操作都是O(log k)总复杂度O(n log k)。空间上只维护了k个元素的堆所以是O(k)。这个结论要注意和“建堆O(n)”区分如果是把整个数组原地建堆建堆本身确实是O(n)但后续每弹出一次还需要O(log n)调整。最小堆方案的O(n log k)是全遍历小堆调整不是建堆复杂度。实测下来在n 10^6、k 10000时快选的运行时间大约是堆方案的三分之一到二分之一。因为快选平均只做2n次左右比较而堆需要每个元素都做log k次堆化常数较大。但当k很大时比如k 500000堆的空间和调整次数都会上升快选的优势也会被拉近这时堆的稳定性价值就体现出来了。没有绝对的“最快”只有适不适合场景。5. 从这题延伸出去的热点话题5.1 刷题热搜背后数组基础查漏补缺从最近的热搜词来看很多人搜“数组初始化”“JS数组排序的几种方法”“指针数组”“二维数组”这类基础问题。这说明215题真正卡住的可能不是“第K大”这个概念而是最基础的数组操作。数组是所有语言的基本功但每门语言的默认行为差别很大。举几个实际对比Java里int[] arr new int[5]默认全是0Integer[]默认全是null。C语言局部数组如果不初始化里面是随机垃圾值这一点经常让新手莫名越界。Python列表切片是浅拷贝修改切片里的元素不会影响原列表。JS数组的sort默认按字符串排所以必须传比较函数很多人在这里翻车。C的int* p[10]是指针数组int (*p)[10]是数组指针含义完全不同。这些细节和215题没有直接关系但如果你连“数组元素访问”“原地修改是否影响外部变量”都没搞清那堆和快选的代码写出来也很容易在边界细节上出错。我的建议是先花半天时间把一门语言的数组特性彻底捋一遍再回头刷数组类题目效率会高很多。5.2 树状数组、动态规划和215的真实关系热搜词里还出现了“树状数组模板”“hot100动态规划”很多初学者可能会疑惑求第K大是不是也可以用树状数组或动态规划这里直接说结论215题本身完全不需要树状数组和动态规划用它们属于杀鸡用牛刀。树状数组擅长的是“单点修改、区间求和”典型场景是前缀和、逆序对、动态维护排名。如果数组范围很小你需要频繁查询“当前第K大”确实可以用值域树状数组加二分但那是一个更复杂的问题形态和215这种“一次性查询”不是一回事。动态规划则适合解决“最大子数组和”“最长上升子序列”“买卖股票最佳时机”这类有最优子结构的问题和第K大没有交集。刷题时要学会判断题型别看到难题就想着上高级数据结构有时候一个堆或者一次分区就能解决。当然如果你已经能轻松写出215题的堆解法和快选解法再用树状数组做一遍“动态第K大”的进阶题是一个很好的扩展练习。但那是第二阶段的事第一阶段先把基本盘打牢。5.3 从215延伸的练习清单与刷题节奏这题做完之后强烈建议按下面的顺序做一轮延伸不然很容易“背过就忘”。最小的K个数剑指Offer 40几乎就是215的反向题用大顶堆或者快选都能练手。前K个高频元素堆排序加哈希统计先统计频率再维护大小为K的最小堆。数据流的中位数用两个堆大顶堆小顶堆维护中位数是215堆思路的经典延续。合并K个升序链表用堆来维护K个链表的当前最小节点非常考验堆的灵活运用。有序矩阵中第K小的元素可以用二分加计数也可以用小顶堆多路归并。刷题节奏上我的个人习惯是第一遍先不管时间复杂度和最优解能AC就行第二遍再尝试把复杂度压下来比如这道题先用排序写一遍再改成堆再改快选第三遍合上书手写代码不看任何参考。这样三轮下来这题才能在真正面试时成为你的熟练题。最后分享一个我实际使用的小习惯不管是堆还是快选写完后都立刻用[3,2,1,5,6,4], k2这组样例在脑子里过一遍再单独检查k1和kn这两个边界。很多线上提交错误都是栽在边界上而不是算法主体上。215题值得多写几遍它看起来简单却能把一批人的算法功底看得明明白白。
数组中的第K个最大元素：从排序、最小堆到快速选择全解析
第一次在力扣hot100里刷到“数组中的第K个最大元素”这道题时我第一反应和大多数人一样“这不就是排序吗”排个序按下标取一下完事了。直到有次模拟面试面试官追问了一句“如果数组长度有10亿内存只能放100个元素你还怎么排序”我才意识到这道题真正要考察的并不是“会不会排序”而是对Top K问题的理解深度。作为力扣hot100里的常客215题几乎出现在各个阶段的算法面试中从校园招聘到社招都可能碰到原题或变体。它看起来只有一行描述却串起了排序、堆、快速选择、分治这些高频核心算法。无论你是在刷题冲刺面试还是单纯想提升代码功底把这一题吃透性价比都非常高。1. 先别急着排序这题到底在考什么1.1 题目表象与真实考点题目描述很简短给定整数数组nums和整数k返回数组中第k个最大的元素。比如nums [3,2,1,5,6,4]k 2结果就是5。注意这里说的是“第k个最大”不是“第k个最小”。一个常见的理解陷阱是把第2大理解成“第二个出现的较大的数”实际上它就是排序后从后往前数第k个元素。这道题表面上是求一个确定的值本质上是一个“部分排序”问题。它的核心矛盾在于你并不需要把整个数组完整地排好序只需要找到“站在第k个位置上的那个元素”。很多人一开始就Arrays.sort()或者nums.sort()虽然能做对但完全没有利用这道题的特殊性。面试官在考察时最关心的是你能不能从“排序”这个舒适圈里跳出来意识到存在更优的选择型算法。用一个生活中的例子来理解你想知道全班同学里身高第三高的人是谁正常思路是让全班按身高排成一列然后数第三个人。但更高效的做法是手里只记下“当前最高的三个人”遍历一遍所有人每看到一个比手里第三名高的就把他替换进来。这样你不需要让全班同学排队只需要记住3个人的信息就够了。215题考察的就是这种“不需要全排序只要局部信息”的思维。1.2 为什么排序不是最佳答案先给排序一个公平的评价用排序解题代码最简单逻辑最不容易错作为第一版答案完全没毛病。但时间复杂度是O(n log n)空间复杂度是O(1)原地排序或O(n)额外数组。这个复杂度在大多数在线评测系统里都能过因为215题的默认数据范围不算极端。但算法面试不只是“能过样例”就行。面试官会继续追问如果n是10的8次方呢如果数据是流式进入的呢如果内存只够保存很小一部分数据呢这时候全量排序立即崩盘。你需要让算法复杂度与“你需要多少信息”相关而不是与“整个数组有多少信息”相关。这里就引出了分层方案排序方案O(n log n)适合一次全量数据、不追求最优的场景。最小堆方案O(n log k)空间O(k)适合k远小于n的场景也天然支持流式数据。快速选择方案平均O(n)最坏O(n²)适合数组已全部在内存中且可以原地修改的场景。计数排序/桶排序如果数值范围有限可以做到O(n 值域)但适用范围窄。BFPRT中位数的中位数最坏也能O(n)但常数较大工程上很少手写面试时提到即可。理解了这个层次你就知道为什么很多大厂面试爱考这题它不考察你是否背得出某个偏门算法而是考察你在不同的资源约束下能不能选出合适的工具并把手上的工具用对、用好。2. 方案一最小堆维护前K大最稳妥的工业级思路2.1 最小堆的思路与复杂度先说一个直觉上很诱人的方案用一个最大堆把整个数组建堆然后连续弹出k次堆顶就是第k大的元素。这个方案的时间复杂度是O(n k log n)。如果k很小比如1或者2确实非常快。但它的致命缺点是空间复杂度是O(n)因为你必须把整个数组都放进堆里。当数据量达到千万、亿级别时这个空间开销会让人很难受。更优雅的方案是维护一个大小为k的最小堆。思路是这样的遍历数组时始终保持堆里存放的是“当前已见过的所有元素中最大的k个”。怎么维护当堆没满时直接往里放当堆满了如果新元素比堆顶还小说明它连目前第k大都进不去直接跳过如果新元素比堆顶大说明它把原第k大挤掉了于是先用新元素替换堆顶再调整堆结构。为什么最后堆顶就是答案因为堆里永远保存着最大的k个数而最小堆的堆顶是这k个数里最小的那个。这个“最小的那个”正是全局第k大。举个例子假设k3你维护的堆里是[10, 9, 8]堆顶是8。新来一个78比7大说明7连前3都进不去新来一个11比8大于是把8踢掉堆变成[9, 10, 11]堆顶变成9。整个过程结束后堆里就是所有数字里最大的3个而堆顶就是第3大。这个方案的时间复杂度是O(n log k)。因为每个元素最多经历一次入堆和一次出堆每一次堆调整都是O(log k)。空间复杂度是O(k)。和全量排序相比它的优势非常明显不需要一次性持有全部数据可以一条条处理流式数据在k远小于n的场景下时间也接近O(n)。2.2 三种主流语言的代码实现用Java实现最直接。Java的PriorityQueue默认就是最小堆没有任何额外的配置public int findKthLargest(int[] nums, int k) { PriorityQueueInteger heap new PriorityQueue(); for (int num : nums) { if (heap.size() k) { heap.offer(num); } else if (num heap.peek()) { heap.poll(); heap.offer(num); } } return heap.peek(); }这段代码里有两个细节需要注意。第一先判断heap.size() k而不是先无条件offer再poll这样可以减少入堆次数尤其是当数组里大量元素比堆顶还小时直接跳过能省下很多次堆调整。第二heap.peek()拿到的是堆顶元素也就是当前堆里的最小值千万不要把它当作“最大值”用。C里要用到priority_queue默认是大顶堆所以需要指定greaterint让它变成小顶堆int findKthLargest(vectorint nums, int k) { priority_queueint, vectorint, greaterint pq; for (int x : nums) { if (pq.size() k) { pq.push(x); } else if (x pq.top()) { pq.pop(); pq.push(x); } } return pq.top(); }Python的heapq模块默认也是最小堆配合一个简单的列表就能用import heapq def findKthLargest(nums, k): heap [] for num in nums: if len(heap) k: heapq.heappush(heap, num) elif num heap[0]: heapq.heapreplace(heap, num) return heap[0]Python里有个小技巧先用heappush再heappop要调整两次堆而heapreplace是先弹出堆顶再插入新元素底层只做一次堆化流程性能更好。如果用的Python版本支持也可以直接用heapq.nlargest(k, nums)[-1]一句话搞定。但面试手写时还是建议写上面这个循环版本更能展示你对堆操作的理解。2.3 面试追问与变体写完最小堆解法后面试官常见的追问方向就来了。第一个方向是“如果k也很大怎么办”。当k接近n时最小堆的空间也接近O(n)时间复杂度接近O(n log n)此时不如直接用快选或者在特定条件下直接用排序。如果数据量真的到内存放不下的程度那就得聊外部排序、多路归并、分布式Top K这些工程话题了。第二个方向是“如果数组是流式的怎么办”。这正是最小堆方案的高光时刻。它不需要一开始就拿到整个数组可以一个一个处理。实际业务里的“实时排行榜”“热门商品Top K”基本都是这个思路维护一个小堆新数据来了就更新堆堆顶永远是最新的第K名。第三个方向是“如果k等于1或者等于n呢”。k1就是求最大值直接一趟遍历取最大就行不需要堆。kn就是求最小值同理。写代码时如果看到这两个边界值可以直接返回max/min既简单又避免不必要的堆操作。3. 方案二快速选择平均线性时间的核心算法3.1 从快排到快速选择快速选择是快排的变体也是很多面试官心里真正想听到的答案。它的核心思想来自快排的partition分区操作选定一个基准元素pivot经过一次分区后pivot会落到它最终应该在的位置。比如按从小到大分区pivot左边的元素都小于等于它右边的元素都大于等于它。这时候pivot的位置pos就是它在有序数组中的索引。于是我们可以做判断如果pos恰好等于我们想要的目标索引target那pivot本身就是答案如果pos target说明答案在pivot右边只需要继续处理右半部分如果pos target说明答案在左边只要处理左半部分。关键就在这里快排需要递归处理两边而快速选择每次只需要处理一边另一边的元素完全不用管。复杂度为什么是O(n)我们用改进的递推来看。第一轮分区需要扫描整个数组代价是n。如果目标落在半边下一轮只需要处理大约n/2个元素代价n/2。再到下一轮n/4依此类推。总代价是n n/2 n/4 ... ≈ 2n所以平均情况下是线性的。但最坏情况非常尴尬如果每次选到的pivot都是当前区间的最小值或最大值那么每轮只能排除一个元素总代价变成n (n-1) (n-2) ...是O(n²)。为了避免这个退化常规做法是随机选pivot让最坏情况出现的概率变得极低。这也是“快速选择”这个名字里“快速”二字的底气来源。3.2 用具体例子跑一遍分区过程看一个具体的例子更容易理解。假设nums [3,2,1,5,6,4]k 2。先把问题转换一下从小到大排序后是[1,2,3,4,5,6]第2大是5它的索引是n - k 6 - 2 4。所以我们要找到最终有序数组中索引为4的那个元素记target 4。第一轮取区间[0, 5]选择pivot 3。从小到大分区后数组可能变成[2,1,3,5,6,4]此时pivot的索引是2。因为2 4说明答案在右半部分于是下一轮只看[3, 5]区间对应元素是[5,6,4]。第二轮在区间[3, 5]里选pivot 5。分区后右区间变成[4,5,6]pivot的全局索引变成4。此时4 target直接返回5整个过程结束。可以对比一下如果第一轮选到的pivot 6那么一次就发现pos 5 target下一轮只需要看[0,4]区间也很高效。快速选择的时间开销主要取决于pivot选得好不好。用随机化之后连续选到很差的pivot的概率几乎可以忽略不计。3.3 随机化快速选择代码与避坑重点给出一个经典的迭代版本避免递归过深。代码按从小到大分区目标索引是n - kint partition(vectorint nums, int left, int right) { int pivotIndex left rand() % (right - left 1); int pivot nums[pivotIndex]; swap(nums[pivotIndex], nums[right]); int storeIndex left; for (int i left; i right; i) { if (nums[i] pivot) { swap(nums[i], nums[storeIndex]); storeIndex; } } swap(nums[right], nums[storeIndex]); return storeIndex; } int findKthLargest(vectorint nums, int k) { int left 0, right nums.size() - 1; int target nums.size() - k; while (left right) { int pos partition(nums, left, right); if (pos target) return nums[pos]; else if (pos target) left pos 1; else right pos - 1; } return -1; }这种写法比双指针partition更容易理解也更好背。核心思想是维护一个storeIndex凡是比pivot小的元素都交换到左边最后把pivot放到它最终位置。注意这里比较条件是nums[i] pivot所以相同元素会被分到右边。如果你面对全重复数组这个写法仍然可能退化但概率已经很低。如果追求更稳可以改成三路分区把等于pivot的元素单独放中间。这个属于进阶优化面试时能说清楚就更好了。手写快速选择时我踩过最多的坑是“索引搞混”。写代码前一定要先在纸上明确题目要的是第k大我们从小到大分区就找n-k这个索引如果你用从大到小分区就找k-1这个索引。两种方式都有人用没有谁绝对更好但必须一致。另外快速选择会原地修改数组。如果面试官强调“不能修改原数组”你需要先拷贝一份再操作或者改用堆方案。4. 踩过的坑与实测对比4.1 边界条件与特殊用例速查表我整理了一张速查表覆盖了最常见的边界情况。这些情况在力扣原题里基本都合法但企业笔试或面试手写时不一定有保证提前判断一下能避免很多尴尬。场景可能现象处理建议数组为空直接越界或返回错误先判空按题目要求返回默认值k 0或k n逻辑错乱非法输入直接抛异常或返回默认值k 1求最大值一趟扫描即可不需要堆或快选k n求最小值一趟扫描即可数组全部相同快选可能退化或返回任意值堆解法稳快选建议用三路分区数组非常大内存受限堆也需要O(k)空间考虑外部排序/多路归并思路题目不允许修改原数组快选导致原数组顺序变化拷贝一份再操作特别说下全重复数组。如果数组是[5,5,5,5,5]找第2大结果当然还是5。堆方案毫无压力。快选用我上面给的普通partition由于所有元素都和pivot相等storeIndex几乎不动最后返回的可能一直是左端点然后递归右边或左边时仍然处理大量重复元素复杂度可能退化。处理办法是使用三路分区把等于pivot的元素集中到中间或者干脆先做一个if (left right)终止条件。4.2 多语言API与索引换算同样是“排序”不同语言的默认行为差很多。比如JavaScript的Array.sort默认按字符串字典序排序所以[10, 9, 2].sort()得到的是[10, 2, 9]不是数值顺序。你需要写成arr.sort((a, b) a - b)。这也是很多前端同学刷题时第一次踩坑的地方。C的priority_queue默认是大顶堆想用最小堆必须写priority_queueint, vectorint, greaterint。Java的PriorityQueue默认是小顶堆而Python的heapq默认也是小顶堆。如果面试官让你用某种语言手写堆你得提前弄清楚这个默认方向否则求第k大可能变成求第k小。索引换算也是重灾区。题目求第k个最大如果你按从小到大排序理解索引是n - k按从大到小理解索引是k - 1。很多解法在讨论区里用从大到小分区代码里直接if (pos k - 1)看着很简洁但容易让人疑惑。我建议统一用从小到大分区加n - k因为这样和“从小到大排序后取倒数第k个”的心理模型一致出错概率低。关于标准库C选手可以考虑直接用nth_element它能保证某个位置上的元素是最终有序状态下的值但注意它是求第n小。比如求第2大nth_element(nums.begin(), nums.begin() nums.size() - k, nums.end()); return nums[nums.size() - k];这个函数底层通常实现为快速选择但面试手写时如果你直接调库很可能被追问“内部怎么实现的”所以我还是建议先能手写再谈优化。4.3 时间/空间复杂度追问怎么答面试官问复杂度时不只是要一个结论还希望你解释推导。快速选择的平均复杂度推导可以用“每轮处理区间近似减半”来理解但更严谨的表述是T(n) T(n/2) O(n)。如果你是用随机化版本还可以说“随机pivot带来的期望复杂度为O(n)”。堆方案的复杂度推导相对简单。每个元素入堆/出堆各一次每次操作都是O(log k)总复杂度O(n log k)。空间上只维护了k个元素的堆所以是O(k)。这个结论要注意和“建堆O(n)”区分如果是把整个数组原地建堆建堆本身确实是O(n)但后续每弹出一次还需要O(log n)调整。最小堆方案的O(n log k)是全遍历小堆调整不是建堆复杂度。实测下来在n 10^6、k 10000时快选的运行时间大约是堆方案的三分之一到二分之一。因为快选平均只做2n次左右比较而堆需要每个元素都做log k次堆化常数较大。但当k很大时比如k 500000堆的空间和调整次数都会上升快选的优势也会被拉近这时堆的稳定性价值就体现出来了。没有绝对的“最快”只有适不适合场景。5. 从这题延伸出去的热点话题5.1 刷题热搜背后数组基础查漏补缺从最近的热搜词来看很多人搜“数组初始化”“JS数组排序的几种方法”“指针数组”“二维数组”这类基础问题。这说明215题真正卡住的可能不是“第K大”这个概念而是最基础的数组操作。数组是所有语言的基本功但每门语言的默认行为差别很大。举几个实际对比Java里int[] arr new int[5]默认全是0Integer[]默认全是null。C语言局部数组如果不初始化里面是随机垃圾值这一点经常让新手莫名越界。Python列表切片是浅拷贝修改切片里的元素不会影响原列表。JS数组的sort默认按字符串排所以必须传比较函数很多人在这里翻车。C的int* p[10]是指针数组int (*p)[10]是数组指针含义完全不同。这些细节和215题没有直接关系但如果你连“数组元素访问”“原地修改是否影响外部变量”都没搞清那堆和快选的代码写出来也很容易在边界细节上出错。我的建议是先花半天时间把一门语言的数组特性彻底捋一遍再回头刷数组类题目效率会高很多。5.2 树状数组、动态规划和215的真实关系热搜词里还出现了“树状数组模板”“hot100动态规划”很多初学者可能会疑惑求第K大是不是也可以用树状数组或动态规划这里直接说结论215题本身完全不需要树状数组和动态规划用它们属于杀鸡用牛刀。树状数组擅长的是“单点修改、区间求和”典型场景是前缀和、逆序对、动态维护排名。如果数组范围很小你需要频繁查询“当前第K大”确实可以用值域树状数组加二分但那是一个更复杂的问题形态和215这种“一次性查询”不是一回事。动态规划则适合解决“最大子数组和”“最长上升子序列”“买卖股票最佳时机”这类有最优子结构的问题和第K大没有交集。刷题时要学会判断题型别看到难题就想着上高级数据结构有时候一个堆或者一次分区就能解决。当然如果你已经能轻松写出215题的堆解法和快选解法再用树状数组做一遍“动态第K大”的进阶题是一个很好的扩展练习。但那是第二阶段的事第一阶段先把基本盘打牢。5.3 从215延伸的练习清单与刷题节奏这题做完之后强烈建议按下面的顺序做一轮延伸不然很容易“背过就忘”。最小的K个数剑指Offer 40几乎就是215的反向题用大顶堆或者快选都能练手。前K个高频元素堆排序加哈希统计先统计频率再维护大小为K的最小堆。数据流的中位数用两个堆大顶堆小顶堆维护中位数是215堆思路的经典延续。合并K个升序链表用堆来维护K个链表的当前最小节点非常考验堆的灵活运用。有序矩阵中第K小的元素可以用二分加计数也可以用小顶堆多路归并。刷题节奏上我的个人习惯是第一遍先不管时间复杂度和最优解能AC就行第二遍再尝试把复杂度压下来比如这道题先用排序写一遍再改成堆再改快选第三遍合上书手写代码不看任何参考。这样三轮下来这题才能在真正面试时成为你的熟练题。最后分享一个我实际使用的小习惯不管是堆还是快选写完后都立刻用[3,2,1,5,6,4], k2这组样例在脑子里过一遍再单独检查k1和kn这两个边界。很多线上提交错误都是栽在边界上而不是算法主体上。215题值得多写几遍它看起来简单却能把一批人的算法功底看得明明白白。
