第K大元素解法：堆排序与快速选择Java实现及复杂度详解

LeetCode 热题100里有一道几乎每个 Java 后端候选人都绕不开的题数组中的第K个最大元素。我第一次在面试现场被问到它时第一反应是Arrays.sort之后取倒数第 k 个结果被面试官一连串“时间复杂度能优化吗数据流场景怎么办”给问住了。后来我把这道题的两个标准解法——堆排序和快速选择——彻底吃透才发现它其实是一把打开 TopK 问题大门的钥匙。这篇文章会把两道解法的原理、Java 实现、复杂度推导以及我实际调试中踩过的坑完整拆开适合准备 LeetCode 刷题、Java 面试八股文以及想搞懂“第 K 大/小元素”这类题通用套路的读者。1. 先把题目嚼碎这题到底在考什么1.1 题目要义与目标索引换算先看题目本身给定一个整数数组nums和一个整数k返回数组中第 k 个最大的元素。注意这里说的是“第 k 个最大的元素”不是“第 k 个不同的元素”。也就是说数组里有重复值时重复值也要参与排序计数。举个例子nums [3,2,1,5,6,4], k 2排序后是[1,2,3,4,5,6]第 2 大元素是 5。如果数组里有重复值比如[2,2,3,1], k 2排序后是[1,2,2,3]第 2 大元素是 2而不是 3。这里新手最容易踩的第一个坑是“第 k 大”和“数组索引”之间的换算。数组升序排序后最小的元素在索引 0最大的元素在索引n-1。所以第 1 大对应索引n-1第 2 大对应索引n-2第 k 大就对应索引n-k。换算成代码就是int target nums.length - k;这个target代表“在升序排列中目标元素所在的索引位置”。后面快速选择解法会频繁用到它理解这个换算比背代码重要得多。我见过不少人在面试时直接写int target k那是在按第 k 小处理结果边界全错一调试就露馅。1.2 三条出路排序、堆、快速选择围绕这道题通常有三条技术路线方案时间复杂度空间复杂度特点全排序后取值O(n log n)O(1)最好写但面试会被追问优化大小为 k 的小顶堆O(n log k)O(k)适合海量数据流k 小时很香快速选择算法平均 O(n)最坏 O(n²)迭代 O(1)平均最快是典型减治思想全排序的思路一句话就能说清Arrays.sort(nums)之后返回nums[n-k]。Java 的Arrays.sort对基本类型数组用的是 Dual-Pivot QuickSort对对象数组用的是 TimSort性能已经很好了。但面试官出这道题从来不是想听你调库而是想看你能不能意识到“找第 k 大根本不需要把整个数组排好序”。这就是后面两种解法的出发点。为什么标题锁定堆排序和快速选择因为这两个方案分别代表了 TopK 问题里最典型的两类解法一类是用堆维护“最大的 k 个数”适合流式数据和海量数据另一类是用 partition 分区思想做减治平均复杂度能压到 O(n)。把这两条路走通遇到前 K 个高频元素、最接近原点的 K 个点、数据流中的第 K 大元素这类变体题都能直接套。1.3 另一条小众路线计数排序/桶排序如果题目额外限制了数据范围比如数组里所有元素都在[0, 10000]之间那还可以用计数排序或桶排序。计数排序的思路是开一个长度为maxValue - minValue 1的计数数组统计每个值出现次数然后从大到小累加计数累加到 k 时对应元素就是答案。这种方案的时间复杂度是 O(n range)当 range 远大于 n 时反而更慢。而且它要求数据必须是整数、范围可枚举。LeetCode 原题的数据范围是-10^4 nums[i] 10^4其实用桶排序也能过但面试官通常希望你先掌握通用解法再提特殊解作为补充而不是上来就开桶。2. 小顶堆解法用堆维护“最大的k个数”2.1 为什么偏要用小顶堆而不是大顶堆这是这道题最经典的一个概念陷阱。很多人一听“找第 k 大”第一反应是“那我要维护一个大顶堆每次把最大的弹出来”。方向反了。我们换个角度想维护一个大小为 k 的小顶堆堆里装的是“当前已经遍历过的元素中最大的 k 个”。因为小顶堆的堆顶是堆里最小的元素所以这个堆顶天然就是“最大的 k 个元素里的最小值”也就是第 k 大的元素。每遍历一个新元素时只需要和堆顶比较如果新元素比堆顶大说明它值得进入“前 k 大阵营”那就把堆顶弹出把它放进去如果新元素比堆顶小或相等说明它连当前第 k 大都挤不掉直接忽略。这里我给一个非常直观的模拟。假设k 3数组依次是[5, 1, 9, 2, 8]遇到 5堆不满直接放入堆为[5]遇到 1堆不满直接放入堆为[1, 5]遇到 9堆不满直接放入堆为[1, 5, 9]遇到 2堆已满2 堆顶 1弹出 1放入 2堆为[2, 5, 9]遇到 8堆已满8 堆顶 2弹出 2放入 8堆为[5, 8, 9]最后堆顶是 5也就是数组中最大的三个数 5、8、9 里最小的那个恰好是第 3 大元素。这个模拟跑完小顶堆的原因就一目了然了用一个能 O(1) 拿到最小值的结构来维护候选集合谁最“菜”谁就先出局。2.2 Java 实现与逐行拆解Java 里实现堆最直接的方式是PriorityQueue默认是小顶堆。完整代码如下public int findKthLargest(int[] nums, int k) { // 默认是小顶堆堆顶永远是最小值 PriorityQueueInteger minHeap new PriorityQueue(k); for (int num : nums) { // 堆还没满直接塞进去 if (minHeap.size() k) { minHeap.offer(num); } else if (num minHeap.peek()) { // 当前元素比堆顶大说明它有资格进入前 k 大 minHeap.poll(); minHeap.offer(num); } // 如果 num 堆顶说明它不是前 k 大直接跳过 } // 堆顶就是最大的 k 个元素里最小的那个即第 k 大 return minHeap.peek(); }这里有几个细节值得单独拿出来说。第一new PriorityQueue(k)里的k只是初始容量不是“最大容量”。Java 的PriorityQueue不会因为你传入k就自动只保留 k 个元素它会根据元素数量自动扩容。所以代码里必须手动控制size这是新手常犯的错我在面试时见过好几个人在这里翻车。第二peek()和poll()的时间复杂度是 O(1)offer()的时间复杂度是 O(log k)。上面的写法先判断num minHeap.peek()再执行poll()和offer()避免了无意义的堆操作。如果写的是“先 offer 再判断 size 是否超 k超了就 poll”虽然结果一样但每次都会多做一次 O(log k) 的堆化数据量大了差距明显。第三PriorityQueueInteger是对象类型对int[]数组需要逐个装箱。Java 的自动装箱会有一定开销但在这道题的量级下完全不是问题。如果你追求极致性能可以自己用数组实现一个二叉堆把比较逻辑内联不过面试笔试里完全没必要。2.3 堆解法的复杂度账怎么算时间上每个元素最多经历一次offer()在堆满后可能还会多一次poll()。PriorityQueue的插入和删除都是 O(log k)n 个元素整体就是 O(n log k)。注意不是 O(n log n)因为我们始终把堆的规模限制在 k 以内。空间上堆里最多存 k 个元素所以是 O(k)。如果 k 很小比如 k 10堆的规模就很小内存开销非常低这正是堆解法在“海量数据 TopK”场景下的核心优势你不需要把所有数据一次性加载到内存只要维护一个容量为 k 的小顶堆就能在 O(n log k) 的时间里得到答案。数据流源源不断来的时候堆解法也能在线处理新来一个元素就更新一次堆。反过来当 k 接近 n 时堆解法就没什么优势了。比如 k n/2那堆的规模是 n/2复杂度退化到 O(n log n)和直接全排序差不多还多堆内存开销。这时候快速选择或者全排序反而更合适。所以面试中如果被问到“k 很大时你怎么办”不能只背一个堆解法。3. 快速选择解法快排思想减一半工作量3.1 快速排序与快速选择的血缘关系快速选择的核心是分区partition而分区正是快速排序的灵魂。理解了这个关系就理解了为什么快速选择平均能到 O(n)。快速排序每一轮会选一个 pivot把数组分成两部分左边都小于等于 pivot右边都大于等于 pivot。关键事实是分区结束后pivot 已经落在它最终的位置上也就是说它左边的元素数量是固定的它在整个数组升序排列中的最终索引就是分区返回的下标。快速选择利用了这一点我们不需要排序整个数组只需要找到目标索引target n - k。每次分区后拿返回的下标p跟target比较p targetpivot 就是这个位置直接返回nums[p]p target目标在右半区丢弃左半区继续在右半区找p target目标在左半区丢弃右半区继续在左半区找因为每轮只需要处理一侧工作量从快速排序的“两个子区间都处理”变成了“只处理一个子区间”这就是减治思想。快速排序复杂度是 O(n log n)快速选择平均降到 O(n)本质原因就在这里。换个更直白的说法快速排序像是一个老师要把全班 50 个人的成绩都排好名次每个环节都要比较所有分区快速选择只是想知道第 10 名是谁每次分区后只要盯着一半区域继续找就行另一半直接扔掉。3.2 分区函数的三种写法和取舍分区函数partition是快速选择的基石写不好整个算法就会出各种边界问题。常见的写法有三种Lomuto 分区、Hoare 分区、三数取中/随机化增强。Lomuto 分区思路最简单选最右边的元素作为 pivot用一个i指针记录“小于等于 pivot 的区域边界”从左到右扫描遇到小于等于 pivot 的元素就把它换到i位置然后i。扫描结束后把 pivot 换到i位置返回i。它的交换次数比 Hoare 多但代码不容易写错是面试首选。Hoare 分区是左右双指针left从左往右找大于 pivot 的元素right从右往左找小于 pivot 的元素找到后交换。它平均交换次数少但循环条件和指针移动的细节很多稍不小心就会死循环或越界。比如两个指针相遇时下标怎么处理、重复元素会不会导致无限交换这些问题在紧张状态下很容易写乱。三数取中和随机化不是分区逻辑本身而是对“选哪个元素当 pivot”的改进。普通 Lomuto 固定选最右元素如果数组本身是近乎有序的分区会严重不平衡。三数取中是从left、mid、right三个位置取中间值当 pivot大概率能让分区均匀一些随机化则是随机选一个下标当 pivot从概率上避免人为构造的最坏输入。两者都只是调整 pivot 的选法不改变分区主体代码。3.3 迭代实现第K大元素完整 Java 代码先看完整实现我下面逐段解释public int findKthLargest(int[] nums, int k) { int n nums.length; int target n - k; // 第 k 大元素在升序排列中的索引 int left 0; int right n - 1; while (true) { int p partition(nums, left, right); if (p target) { return nums[p]; } else if (p target) { left p 1; } else { right p - 1; } } } private int partition(int[] nums, int left, int right) { // 三数取中让 nums[left] nums[mid] nums[right] int mid left (right - left) / 2; if (nums[left] nums[mid]) swap(nums, left, mid); if (nums[left] nums[right]) swap(nums, left, right); if (nums[mid] nums[right]) swap(nums, mid, right); // 把中位数换到最右端作为 pivot swap(nums, mid, right); int pivot nums[right]; // Lomuto 分区 int i left; for (int j left; j right; j) { if (nums[j] pivot) { swap(nums, i, j); i; } } // 把 pivot 放回正确位置 swap(nums, i, right); return i; } private void swap(int[] nums, int i, int j) { int temp nums[i]; nums[i] nums[j]; nums[j] temp; }这里最需要注意的地方是while (true)循环。为什么用死循环而不是while (left right)因为每次分区后p一定落在[left, right]范围内并且只要p ! target我们就会缩小搜索区间区间长度严格递减最终一定会出现p target。所以死循环是安全的不会无限循环。当然用while (left right)并在循环外返回nums[left]也可以但死循环配合立即返回更直观。partition内部的i是“小于等于 pivot 的区域边界”初始是left。扫描时如果nums[j] pivot就把nums[j]换到i位置并让i自增。扫描结束后[left, i-1]都是小于等于 pivot 的元素[i, right-1]都是大于 pivot 的元素最后把最右侧的 pivot 换到i就完成了整个分区。这里nums[j] pivot用的是小于等于。如果改成严格小于会让等于 pivot 的元素全部归到右侧在大量重复元素时可能导致分区不均衡。后面讲三路分区时我会更详细展开。3.4 期望复杂度推导为什么平均是 O(n)快速选择平均 O(n) 的推导不复杂。假设每次分区都能把区间差不多分成两半那么处理规模为 n 的问题时先做 O(n) 的分区然后只需要继续处理规模大约为 n/2 的其中一个子区间于是T(n) T(n/2) O(n)展开是T(n) O(n) O(n/2) O(n/4) ... O(2n) O(n)等比级数求和的结果是 2n所以是线性复杂度。这里的关键是“每轮只处理一侧”如果处理两侧那就是快速排序的 O(n log n) 了。最坏情况发生在每次分区都极度不平衡的时候。比如数组已经升序排列pivot 又固定选最右侧元素那每次分区后左边区间有 n-1 个元素右边为空目标每轮只减少一个元素。此时 T(n) T(n-1) O(n) O(n²)和冒泡排序一样慢。所以工程实现里必须引入随机化或三数取中。随机化能保证在概率意义上很难碰到最坏输入三数取中则让“近乎有序”这类常见数据也不容易退化。两者可以结合比如分区前先做三数取中再随机挑一个。不过 LeetCode 场景下三数取中已经足够安全。4. 复杂度对照与面试选型指南4.1 五种方案的完整对照面试时经常要求你说清楚每种方案的差异我用一张表整理方案时间复杂度空间复杂度适用场景关键优缺点全排序O(n log n)O(1)数据量小或不追求最优最稳妥但面试会被追问小顶堆大小 kO(n log k)O(k)数据流、海量数据、k 较小内存可控但 k 大时退化大顶堆全量O(n k log n)O(n)k 很小且数据能一次性装入需要全量建堆内存 O(n)快速选择平均平均 O(n)最坏 O(n²)迭代 O(1)单次查询、数组可改造平均最快最坏需随机化防御计数/桶排序O(n range)O(range)整数且数据范围有限范围大时不适用我补充一个细节大顶堆全量方案是指先把所有元素放进一个大顶堆堆顶是最大值然后连续poll()k-1 次堆顶就是第 k 大。构建大顶堆的时间是 O(n)poll 一次是 O(log n)整体 O(n k log n)。它能处理 k 特别小的情况但因为需要存下整个数组空间上并不占优工程里很少有人用它替代“大小 k 的小顶堆”。4.2 什么数据会让快速选择翻车快速选择最怕“刻意构造的输入”。经典反例是数组几乎有序pivot 固定取最右侧元素每次分区后另一个子区间都接近空算法退化到 O(n²)。LeetCode 的测试数据一般不会故意恶心你但如果你用固定 pivot 的写法去跑大数据量、几乎有序的用例超时是有可能的。另一个容易翻车的情况是数组里全部是相同元素。Lomuto 分区如果写成nums[j] pivot会把等于 pivot 的元素都放到右侧分区后左边为空右边 n-1 个元素同样退化。解决方法是把比较改成或者直接上三路分区。我在本地跑过[1,1,1,...,1]这种数据三路分区一次就能定位普通 Lomuto 分区用严格小于会退化得很明显。还有个不太起眼但实际存在的问题递归深度。如果递归实现快速选择每次只处理一侧理论上递归深度可能达到 n极端数据下会栈溢出。LeetCode 的评测环境栈很深一般不会爆但如果是自己公司的算法面试现场手写递归被问到“栈溢出怎么办”就很尴尬。所以我的建议是直接写迭代版本这是工程上更稳妥的选择。4.3 面试官追问时怎么答这题在面试里几乎必然是连环追问的。我把我被问过的问题和合理答法整理了一下。问“时间复杂度是多少能不能证明”这是送分题答平均 O(n)展开等比级数求和然后主动补一句最坏 O(n²)再说我用了三数取中/随机化来避免最坏情况。整套回答行云流水比只说“平均O(n)”好太多。问“这个算法能处理数据流吗”不能。快速选择必须拿到全量数组才能做分区数据流场景应该用小顶堆堆里维护最大的 k 个新元素来了实时更新。这道题在“大数据面试题”里经常和海量数据处理一起出现堆解法是那一类问题的标准答案。问“如果 k1 或 kn 呢”快速选择只需要一次分区就能找到答案堆要遍历完整个数组才能确定堆顶。单次查询场景下快速选择更优。但如果是持续查询比如“不断有新元素进来随时问当前第 k 大”那只能靠堆。问“内存装不下整个数组怎么办”那就不能全排序也不能快速选择只能分批处理维护一个大小为 k 的小顶堆从磁盘一部分一部分读数据更新堆。这其实就是海量 TopK 的标准解法。5. 工程化细节把解法磨成生产级代码5.1 随机化 pivot一句话消灭最坏输入三数取中能应对“近似有序”的数据但严格来说它仍然是一种固定策略如果攻击者知道你的取法还是可能构造出坏数据。最稳妥的做法是随机化int randomIndex left ThreadLocalRandom.current().nextInt(right - left 1); swap(nums, randomIndex, right);ThreadLocalRandom是 Java 并发包里的工具在当前线程内生成随机数比new Random()的开销更低。代码放在partition的最前面选中随机下标后把它和right位置的元素交换后续走 Lomuto 分区的逻辑完全不用改。随机化解决的是“策略被预测”的问题。因为每次选 pivot 的位置是随机的理论上任何输入被分到极不平衡两侧的概率都极低最坏情况只能靠“运气特别差”才会出现。在线判题环境里随机化算法依然能保证正确性只是运行时间可能会有微小波动。我可以给出一个实测经验固定 pivot 的快速选择在 LeetCode 的 215 题上跑大数据量时偶有超时风险加上随机化后基本都能稳过。如果你的代码在本地没问题但提交超时优先检查 pivot 选法。5.2 重复元素与三路分区当数组里重复元素很多时普通 Lomuto 分区的问题在于等于 pivot 的元素会被随机分配到左右两侧导致分区结果不稳定。一种更强悍的做法是荷兰国旗三路分区把数组一次性分成三段小于 pivot、等于 pivot、大于 pivot。这样等于 pivot 的一整块可以在一步内确定位置不需要再参与后续递归。核心思路是用三个指针lt、i、gtprivate int[] partitionThreeWay(int[] nums, int left, int right, int pivot) { int lt left, i left, gt right; while (i gt) { if (nums[i] pivot) { swap(nums, lt, i); } else if (nums[i] pivot) { swap(nums, i, gt--); } else { i; } } // 返回等于 pivot 的区间 [lt, gt] return new int[]{lt, gt}; }如果目标索引target落在[lt, gt]区间内直接返回pivot即可。如果target lt只需要处理左段如果target gt处理右段。对于全数组都是同一个值的极端情况三路分区一次就结束时间复杂度 O(n)。不过这道题用不用三路分区要看情况。LeetCode 的测试数据里重复元素比例不高普通 Lomuto 加三数取中完全够用。但如果面试官特意问“数组里全是重复元素怎么办”三路分区就是很漂亮的加分答法。我建议两者都掌握写代码时优先用三路分区思路边界更不容易错。5.3 边界保护和健壮性细节有几个实现细节看起来小实际出问题概率很高我单独列出来。第一中间下标计算一定要写成left (right - left) / 2不要写成(left right) / 2。虽然这两个表达式在大多数情况下结果一样但当left right超过 int 最大值时会溢出结果变成负数导致数组越界。这道题 n 一般不大但养成这个习惯很重要。第二swap操作要让两个下标不相等时才执行或者直接交换也无所谓。交换时如果i j纯属白做一次但对性能影响极小。真正需要注意的是 Lomuto 循环里swap(nums, i, j)的i和j可能相等如果你在swap里用了临时变量这种自交换没有任何问题。第三快速选择是原地修改数组的。如果你不希望原数组被破坏需要先nums.clone()再操作。刷题时直接修改原数组没问题但真实业务代码里对外提供的 API 最好别改调用方的数组否则会有隐蔽的副作用。第四k的边界。k 1时target n-1处理的始终是最大值k n时target 0处理的是最小值。这两个边界在快速选择里都能自然收敛。堆解法在k 1时堆里始终只保留当前最大值逻辑也正确。6. 踩坑实录与同类题扩展6.1 我实际踩过的几个坑第一个坑把PriorityQueue当成“自动限制容量为 k”的容器。我第一次写堆解法时天真地以为new PriorityQueue(k)会自动只保留 k 个元素结果堆里越长越大返回的堆顶根本不是第 k 大。后来意识到必须手动判断 size这个错误才彻底改掉。第二个坑快速选择的 target 换算写反。我把“第 k 大”误写成“第 k 小”target k - 1然后用升序 partition 去找结果测试用例全错。排查了很久才发现问题出在这一行。后来我每次写这题第一行都先注释// target n - k因为升序数组里第 k 大在索引 n-k。听起来很傻但真的能救命。第三个坑Lomuto 分区写成了严格小于。nums[j] pivot在大多数用例下也能跑对但遇到大量重复元素时退化成 O(n²)。有一次我拿着这段代码去跑一个全为 1 的 10 万长度数组跑了半天没结束。改成之后瞬间出结果。这让我养成了一个习惯每次写完快速选择本地先压测三组数据随机数组、近乎有序数组、全相同数组。第四个坑while (true)循环里返回点写错。我早期的代码是在partition返回后直接return nums[p]但忘了判断p是否等于target结果很多时候返回的只是一个随机 pivot 值问题表现非常诡异。后来我强制自己在循环里只做两件事比较p和target更新left/right其他一律不写逻辑就清晰了。6.2 从这题延伸出去的一串 LeetCode 热题这道题最厉害的地方是它连通了一大片 TopK 类问题属于热题100里的“枢纽题”。我建议刷完它之后马上做下面这几道能明显感觉到套路复用数据流中的第 K 大元素小顶堆解法的直接应用维护大小为 k 的堆每个新元素进来都更新堆返回堆顶。这题和 215 几乎一个模子。前 K 个高频元素先用哈希表统计频率再用大小为 k 的小顶堆按频率排序。核心还是“维护一个容量为 k 的候选集合”。最接近原点的 K 个点把距离算出来放进堆里堆大小 k按距离比较。本质依然是 TopK。根据字符出现频率排序哈希统计加桶排序或堆排序重点练“统计排序”组合。另外热题100里的 994 腐烂的橘子、073 爱吃香蕉的狒狒、224 基本计算器这些题虽然解法不同但它们在“细节边界多”这一点上和 215 很像。刷 215 时你会养成一个习惯反复验证索引边界、处理重复值、考虑最坏数据这个习惯迁移到 BFS 和栈模拟的题目里同样有用。我个人在实际刷题和面试复盘中的体会是TopK 题先问自己三个问题——k 有多大数据能一次性放内存吗数据有没有大量重复把这三个问题想清楚用堆还是用快速选择其实马上就能判断。还有一点不要只背代码要在本地把数组改成几乎有序、全相同、含负数等边界情况分别跑一遍很多隐藏问题只有在这种压测下才会暴露。这道题刷透之后你会发现自己在处理“海量数据第 K 大”类问题时思路会清晰很多。