★ FEATURED ARTICLE 第一次在模拟面试里看到“数组中的第K个最大元素”这道题时我内心是有点不屑的这不就是排序之后按下标取吗一行Arrays.sort就能收工有什么好问的。直到面试官追问了一句“如果数组有 1 亿个数内存只够装下 100 万个数呢”我才意识到自己压根没读懂这道题在考什么。后来刷得多了才发现这是一个经典的“选择问题”考察的不是你会不会排序而是你会不会根据场景选择算法和数据结构。如果你是准备算法面试的开发者或者在实际工作中需要处理 Top K、中位数、海量数据排序这类问题这篇文章应该能帮上忙。我会把这道题的完整思路拆开讲从最直觉的排序解法开始再讲堆和快速选择两种主流方案包括复杂度推导、边界条件、面试追问以及从这道题延伸出去的一系列实战技巧。1. 题目卡片与直觉陷阱为什么第一反应不该是排序1.1 先搞清楚题面在说什么这道题的标准描述很简单给定一个未排序的整数数组nums和一个整数k返回数组中第k个最大的元素。注意是“第 k 个最大”不是“第 k 个最大不重复”。举例来说数组[3,2,3,1,2,4,5,5,6]k 4答案是4。因为从大到小排列是6,5,5,4,3,3,2,2,1第 4 个数是4。有的读者可能会疑惑有两个 5那第 3 个是 5 还是 4这就是关键——题目要求的是“排名”5 出现在第 2 和第 3 位所以第 4 位自然落到 4重复元素也要参与排名不能去重。这个定义直接决定了后续写代码的方式也决定了快速选择里partition之后判断下标的逻辑。如果不先把这个定义捋清楚后面很容易把下标算错尤其当你习惯把第 k 大转换成“正数第 n-k1 小”的时候。1.2 排序解法能过但面试官的笑容会消失最直接的思路就是先排序再取元素。降序排列取下标k-1升序排列取下标n-k。两种写法本质一样很多人喜欢用升序因为系统默认排序函数都是升序的。代码大概长这样public int findKthLargest(int[] nums, int k) { Arrays.sort(nums); return nums[nums.length - k]; }复杂度是O(n log n)空间复杂度取决于排序实现一般可以视为O(1)或O(log n)。如果是在笔试环境数据规模只有几千几万这么写完全能通过而且不容易出错。但在面试里这种解法只能作为一个铺垫不能作为终点。原因是排序做了太多“无用功”我们只需要知道第 k 个数是什么排序却把所有元素的大小关系都理清了相当于为了找一个班级里第三高的人先把全班同学按身高完整排序一遍。更关键的是排序解法的复杂度下限就是O(n log n)而后面的快速选择平均能到O(n)。在实际场景里O(n log n)和O(n)的差距在数据量大的时候是肉眼可见的。所以面试官问这道题很大概率就是想看你会不会跳出“排序思维”选择更合适的工具。这不是说排序解法没有价值而是你要能清晰地回答“为什么还能更快”。2. 快速选择把“找第K大”变成“排除错的答案”2.1 从快速排序的 partition 讲起快速选择Quick Select的核心思想来自快速排序里的partition操作。partition做的事情是选定一个基准元素pivot把数组重排成两部分一部分小于pivot一部分大于等于pivot最后返回pivot落在的位置。这个位置本身就是一个排序后的信息如果返回的下标是i那说明pivot已经是数组里第i1小的元素。我们可以做个类比。假设全班同学在操场上排队你想找第三高的人。你随便拉一个人出来当“标杆”让他站在中间然后指挥比他矮的站左边、比他高的站右边。如果这个标杆站到了第 15 位说明第三高的人一定在右边那一堆里左边那 14 个人就没有再看的必要了。下一次再在右边堆里随便拉一个标杆重复这个过程。每一次操作都能排除一大批“不可能是答案”的元素。这就是快速选择的基本逻辑不需要把整个数组排好只需要在partition之后判断pivot的位置和k的关系决定继续处理左边还是右边。2.2 复杂度期望分析与最坏情况为什么快速选择的期望复杂度是O(n)这里有个很直观的推导。假设每次partition比较理想pivot 大概落在数组中间的位置那么你只需要处理一边问题规模从n减到约n/2。于是总工作量是T(n) n n/2 n/4 n/8 ... 2n这个等比级数收敛到2n所以平均复杂度就是O(n)。这是排序做不到的。但要注意这是“期望复杂度”不是“最坏复杂度”。如果每次选 pivot 都选到当前区间的最小值或最大值那么每次partition只排除一个元素剩下的区间还是n-1、n-2、n-3... 这样一路下来工作量就变成T(n) n (n-1) (n-2) ... 1 n(n1)/2也就是O(n^2)。最坏情况和选择 pivot 的策略强相关所以工程实现里几乎都要做“随机化”随机选一个位置作为 pivot让最坏情况出现的概率变得极其微小。这是概率层面的保证不是玄学。只要 pivot 在整个数组里不是特别偏比如每次都在数组的前 10% 或后 10%依然能得到近似线性的性能连续很多次都选到极端值的概率会随次数增加而指数级下降。partition本身是O(n)的快速选择只处理一侧而且不用像快速排序那样对两侧都递归所以能突破nlogn的下限。这也是为什么面试官愿意看到这种解法因为它体现的不是堆栈层面背题的记忆而是对分治思想的真正理解。2.3 完整代码实现与随机化优化以升序下标为目标来写会比较顺第 k 大的元素在升序排列后的下标是n-k。我们把问题转换成“找升序数组中下标为n-k的元素”。Java 实现大概是下面这样class Solution { public int findKthLargest(int[] nums, int k) { int targetIndex nums.length - k; return quickSelect(nums, 0, nums.length - 1, targetIndex); } private int quickSelect(int[] nums, int left, int right, int targetIndex) { if (left right) { return nums[left]; } int pivotIndex partition(nums, left, right); if (pivotIndex targetIndex) { return nums[pivotIndex]; } else if (pivotIndex targetIndex) { return quickSelect(nums, pivotIndex 1, right, targetIndex); } else { return quickSelect(nums, left, pivotIndex - 1, targetIndex); } } private int partition(int[] nums, int left, int right) { int randomIndex left new Random().nextInt(right - left 1); swap(nums, randomIndex, right); int pivot nums[right]; int i left; for (int j left; j right; j) { if (nums[j] pivot) { swap(nums, i, j); i; } } 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; } }这里partition用的是“挖坑 双指针”的变形先把随机选的 pivot 换到最右边然后遍历从左到右right-1的元素比 pivot 小的都换到前面去最后把 pivot 放到i的位置。这个写法不容易弄乱边界也比经典霍尔分区更容易理解。还有一个细节quickSelect的递归退出条件是left right。因为题目保证1 k nums.length所以 targetIndex 一定在数组范围内递归一定会收敛到正确位置不需要再检查left right这种异常情况。2.4 为什么这不是“玄学”概率层面的解释很多人第一次看到快速选择会担心万一随机化效果不好怎么办这里可以再深挖一层。每次随机选 pivot选到数组大小中间 50% 的区间的概率是 50%。也就是说每次递归至少还能把数组规模缩小一半左右的概率是 1/2。按这个期望算递归深度和总工作量依然是线性的。这跟“抽卡”不一样不是赌运气而是通过随机化让最坏情况的概率在工程上可以忽略。如果实在不放心随机数也可以使用“三数取中”取left、mid、right三个位置的中位数作为 pivot能有效避免几乎有序的数组退化到O(n^2)。不过在在线判题场景下随机化通常已经足够稳定了。我在本地测试过一个 100 万随机整数的数组找第 500 大的元素快速选择大概只需要 50 毫秒左右而完整排序要 300 毫秒以上差距非常明显。3. 堆解法Top K 问题的通用武器3.1 小顶堆存 Top K 的思路第二种经典解法是用堆而且用的是小顶堆不是大顶堆。这个点很多人一开始会绕不过来既然是找第 k 大的为什么不用大顶堆你想一下如果我们要保留数组中最大的 k 个数用一个小顶堆来维护这 k 个数。堆顶是这 k 个数中最小的那个也就是第 k 大的候选。具体操作是这样的遍历数组当堆的大小还不到 k 时直接加入。一旦堆满 k 个元素就检查当前元素和堆顶的大小关系。如果当前元素比堆顶大说明堆顶已经被挤出了“最大的 k 个数”之列我们弹出堆顶把当前元素加进来。整个数组遍历完后堆里留下的就是最大的 k 个数而堆顶恰好是这 k 个数中最小的那一个也就是整个数组的第 k 大元素。可以这样理解有一个能容纳 k 个人的排行榜新来的人分数比当前最后一名高就顶掉最后一名分数不如最后一名就什么都不做。遍历结束后榜上最后一名就是整个 k 人榜的守门员也就是第 k 大。3.2 代码实现与复杂度拆解Java 里的PriorityQueue默认就是小顶堆代码特别简洁class Solution { 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()) { minHeap.poll(); minHeap.offer(num); } } return minHeap.peek(); } }时间复杂度是O(n log k)。因为每个元素可能进堆一次也可能不进但最坏情况下每个元素都需要一次堆调整堆操作的单次复杂度是O(log k)。如果 k 远小于 n比如找一万个数里的第 10 大这个算法的速度接近O(n)实际运行非常快。空间复杂度是O(k)也就是堆的容量。有一个很容易踩的坑如果你用的是大顶堆然后打算连续弹出k-1次来得到第k大那么总复杂度会变成O(k log n)。假设k和n同量级比如找中位数k n/2复杂度就退化成了O(n log n)和排序没有区别。堆解法的优势只在“k 远小于 n”时才能充分发挥这一点面试时一定要能讲清楚。3.3 数据流场景的延伸海量数据怎么办堆的另一个优势是天然支持流式数据。在线判题里我们面对的是完整数组但真实工程中经常是数据源源不断产生比如一批批日志、一条条用户点击记录。你不可能等到所有数据都到齐再去排序这时候小顶堆提供了一个很好的在线维护方案不管数据来了多少堆里始终维护着当前出现过的最大的 k 个元素随时可以查询当前的第 k 大。我做过一个类似的功能一个数据上报系统需要实时统计每分钟请求量的 Top 100。早期做法是每五分钟把全量数据拉出来排一次序数据量一大耗时直线上升。后来改成“堆 定时聚合”的思路每来一条数据就往堆里尝试插入查询时只取堆顶整个接口的耗时就基本稳定在常数级别。这也是为什么面试里只要出现“第 k 大”“Top K”这些关键词堆几乎是第一个要想到的答案。4. 面向面试的解法选择策略4.1 三种解法对比先把三种方案的核心指标放在一起看。解法时间复杂度空间复杂度是否适合流式数据适合场景排序O(n log n)O(1) 或 O(log n)否数据量小、追求最简单实现快速选择O(n) 平均、O(n^2) 最坏O(1)否静态数组、目标明确、能接受修改原数组堆O(n log k)O(k)是海量数据、k 较小、流式处理这张表在面试时很有用。面试官问“为什么不用排序”你可以说排序的复杂度更高问“为什么不用快速选择”你可以说它可能退化而且需要修改原数组问“为什么不用堆”你可以说当 k 接近 n 时堆的复杂度优势就不明显了。4.2 面试官追问时怎么回答这道题的高频追问基本集中在三个方向。第一个是数据规模“如果内存放不下整个数组怎么办”这时候排序和快速选择基本出局用堆做在线维护是标准答案甚至可以用“多路归并 小顶堆”处理分布在多台机器上的数据。第二个追问是“能否保证复杂度稳定”快速选择有最坏情况O(n^2)的问题你可以用随机化降低概率但如果面试官要求最坏情况也得是O(n log n)比如找中位数那可以用BFPRT算法不过正常面试很少要求到这个深度。第三个追问是“如果 k 非常小比如 k 1 怎么办”这是个送分题答案是直接线性扫描一遍找最大值。但这个追问背后隐藏的逻辑值得思考没有万能的算法都是根据参数选择策略。k1 的时间复杂度应该是 O(n)快速选择和堆都可以做但线性扫描最简单。4.3 常见的错误实现我也见过不少同学在写快速选择时翻车最常见的是partition循环条件写错。比如用while (i j)双指针向内逼近的写法有两个元素时容易在i j后继续交换导致死循环或下标越界。我习惯把 pivot 先换到最右边然后用单项扫描的写法可以在很大程度上避免这类边界问题。还有一个错误是把第 k 大误认为是下标k。因为第 k 大在升序数组中的下标是n-k不是k也不是k-1。如果nums [3,2,1,5,6,4]k2正确答案是 5写错下标的人可能会得到 3。这个问题在初学阶段几乎人人都会踩建议从题目定义出发先手动算一遍示例把目标下标算明白再动代码。5. 边界条件和细节陷阱提交通过只是开始5.1 边界测试不能省这道题虽然看着简单但边界条件很容易闹出 Bug。先列几个我常用的测试用例nums [1],k 1期望结果是 1。这时候排序解法和快速选择都只有单元素分支要注意递归不会坏。nums [1, 2],k 2期望结果是 1。这里的targetIndex是 0快速选择要能处理left right直接返回的情况。nums [3,2,3,1,2,4,5,5,6],k 4期望结果是 4。这个用例里有很多重复元素能验证“重复值也要参与排名”的定义。nums [-1, -2, -3],k 1期望结果是 -1。负数和大数边界不能忽略否则比较逻辑有可能被忽略。快速选择还有一个隐藏问题因为会修改原数组如果业务上要求原数组不变就需要在函数开始时复制一份或者改用堆解法。面试中如果没额外说明一般可以直接修改nums但最好先问一句“这道题允许修改传入的数组吗”这个细节在真实的面试官眼里是个加分项。5.2 重复元素的含义重复元素是另一个容易犯错的地方。题目里的“第 k 个最大元素”指的是排序后位置排名而不是把重复元素去重后再排名。前面已经用[3,2,3,1,2,4,5,5,6]举例了两个 5 占两个位置因此第 4 大是 4 而不是 5。如果你的实现里用了Set去重结果就错了。快速选择处理重复元素时partition的结果也要特别留意。上面的实现把等于 pivot 的元素放在右边也就是“小于 pivot”在左“大于等于 pivot”在右。这样做的好处是即使有大量重复值也不会因为 pivot 的移动导致左边和右边分类不清。如果你把相等元素也放到左边最终返回的pivotIndex可能无法准确反映这个元素在全数组中的排名后面的判断就容易出错。5.3 工程视角为什么面试题和线上代码不一样这道题在线判题环境里可以通过不代表线上系统可以照抄。真实业务里你很少遇到只找一个k的场景更多是要持续维护一个 Top 榜单或者偶尔查询第 k 位。这时候堆的优势就更明显。另一方面线上环境的数据分布往往不是随机数而是带业务特征的数据比如商品售价可能大量集中在 100 元附近。这时候快速选择的随机化策略仍然有效但如果你用的是“固定取第一个元素作为 pivot”一个几乎降序的输入会把算法打到最坏复杂度。我见过有同事在线上代码里用nums[left]当 pivot上线之后遇到某段时间数据恰好有偏接口从几十毫秒掉到秒级。排查了半天才发现是 quick select 的 pivot 选法太死板换成随机 pivot 之后恢复正常。这也是为什么我一直强调简单写法可以过笔试但生产代码一定要做随机化或者至少加一道“三个候选位置取中位数”的保护。6. 从这道题延伸出去Top K 类问题的思维框架6.1 高频变形题该怎么套“数组中的第 K 个最大元素”是很多 Top K 问题的基础模板。常见的变形包括求数组中最小的 k 个数其实就是第 k 小问题等价于把原题第 k 大换成第n-k1大或者直接用partition反向判断。数据流中的第 k 大元素常见做法就是在初始化时用前 k 个元素建小顶堆之后每次进来一个新元素执行一次“打擂台”操作复杂度是O(log k)。求无序数组的中位数本质是找第n/2大的元素用快速选择平均可以做到O(n)。求出现频率最高的 k 个词经典方案是先遍历一遍统计频率再用大小为 k 的小顶堆按频率筛选。两个有序数组合并找第 k 小常见做法是二分查找而不是把两个数组真正合并。这些题都有一个共同点你需要明确“排名标准的定义”“数据是否能一次性装入内存”“是否需要在线查询”这三个问题然后再决定用哪套方案。面试时只要能把思路落到这三个问题上大部分 Top K 变形题都能很快打开局面。6.2 遇到限制时的策略有时候题目会对空间有严格限制比如“内存只允许额外使用O(1)”。这时候堆解法就不符合要求了因为堆需要O(k)空间。如果数据是静态的可以用快速选择因为它只用递归栈的O(log n)空间而且用“尾递归 循环”的方式甚至可以把空间压到真正的O(1)。如果连修改数组都不允许快速选择就需要先复制一份数组空间复杂度变成O(n)此时未必比堆更划算。还有一种场景是数据量非常大比如上亿条记录、内存无法全部加载这时可以把数据分成多个文件分片每片用小顶堆求出局部的 Top K最后再对每片的 Top K 做一轮归并。这种“分治法 堆”的组合在真实的海量数据处理里非常常见也是面试加分项。6.3 我的实操心得最后分享一点个人经验。刷这道题时我建议至少把三种解法都手写一遍排序解法用来热身快速选择用来理解分治和 partition堆解法用来熟悉“小顶堆存 Top K”这个套路。写完代码之后一定要跑几个自己在脑海里构造的边界用例尤其是只有一个元素、所有元素都相等、以及 k 恰好等于数组长度的场景。我在实际做项目时最常用的其实是堆因为业务需求基本都是“持续得到 Top 100 榜单”而不是“一次性求第几个最大值”。但面试时我最喜欢用快速选择回答因为它能展示更深层的算法功底。两者没有优劣关键是你能迅速判断题目背后的约束条件并准确说出自己的思路。这道题刷完之后你可以再找几道类似题目练手重点不是背答案而是把“选择问题”的思维框架烙进脑子里以后遇到任何 Top K 变体都能快速定位到合适的数据结构和算法组合。
阅读完成 · 觉得有帮助？
