LeetCode 215 数组中的第 K 个最大元素题解排序、小顶堆与 Quick Select 三种思路深度剖析【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode本篇技术指南以开源仓库 leetcode 中 problems/215.kth-largest-element-in-an-array.md 为主体系统讲解「数组中的第 K 个最大元素」这道高频面试题的三种经典解法——排序、固定大小为 K 的小顶堆、以及基于 partition 的 Quick Select。读者读完将掌握「第 K 大/第 K 小」类问题的通用套路何时选择 O(nlogn) 排序、何时用 O(n·logk) 堆、何时用平均 O(n) 的快速选择并能把「固定堆」技巧迁移到数据流中位数、有序矩阵第 K 小元素等进阶题目上。题目描述在未排序的数组中找到第 k 个最大的元素。请注意你需要找的是数组排序后的第 k 个最大的元素而不是第 k 个不同的元素。示例 1输入: [3,2,1,5,6,4] 和 k 2 输出: 5示例 2输入: [3,2,3,1,2,4,5,5,6] 和 k 4 输出: 4说明你可以假设 k 总是有效的且1 ≤ k ≤ 数组的长度。原文档problems/215.kth-largest-element-in-an-array.md同时给出了前置知识与题目背景本题需要掌握「堆」与「Quick Select」两项前置技能并在国内大厂面试中频繁出现原文档标注的公司有阿里、腾讯、百度、字节。前置知识堆与 Quick Select堆的核心动态求极值仓库 thinkings/heap.md 用「一个中心」总结了堆的本质——动态求极值动态与极值二者缺一不可。堆对外只暴露两个核心 APIpush推入一个数据内部组织方式对调用方透明pop弹出一个数据弹出的一定是最小值小顶堆或最大值大顶堆。正因为堆能随时弹出当前极值且插入、弹出都是 O(logn)它天然适合「数据不断变化、需要反复取极值」的场景。求「第 K 大」可以看作动态求极值的连续过程先求最大值并弹出再求剩余数据中的最大值就是第 2 大……不过这样做需要反复弹出 K 次聪明的做法是下面要讲的「固定堆」。Quick Select快排思想的减治Quick Select 源自快速排序的 partition 过程但它只处理包含答案的那一半区间而不是对整个数组排序因此平均复杂度可以降到 O(n)这正好呼应仓库 thinkings/binary-search-1.md 中的观点求第 K 大小的值既可以用堆也可以用二分/减治思想两者思路完全不同。解法一直接排序O(nlogn)最直观的解法就是给数组排序求解第 K 大的数等价于从小到大排好序的数组中的第(n-K)小的数n 是数组长度。例如[3,2,1,5,6,4], k 2 1. 数组排序 [1,2,3,4,5,6] 2. 找第n-k小的数n-k4, nums[4]5即第2大的数时间复杂度O(nlogn)n 为数组长度。空间复杂度取决于排序实现通常为O(logn)快排递归栈或O(1)原地堆排序。Java 实现来自原文档class KthLargestElementSort { public int findKthlargest2(int[] nums, int k) { Arrays.sort(nums); return nums[nums.length - k]; } }这是最简单、最容易写对的解法适合面试开头快速给出正确解再逐步优化。解法二固定大小为 K 的小顶堆O(n·logk)思路维护一个大小为 K 的小顶堆堆顶是最小元素。扫描一遍数组每当堆的size K时删除堆顶元素。扫描结束后堆中保留的就是最大的 K 个元素而堆顶正是这 K 个最大元素中最小的那个——也就是整个数组的第 K 大元素直接返回即可。为什么用小顶堆而不是大顶堆因为我们要淘汰的是「当前最小的」让小顶堆的堆顶始终是堆内最小值一旦堆内元素超过 K 个就弹出堆顶从而保证堆内永远是当前见过的最大的 K 个数。这正是仓库 thinkings/heap-2.md 中总结的「固定堆」技巧固定一个大小为 k 的大顶堆可以快速求第 k 小的数反之固定一个大小为 k 的小顶堆可以快速求第 k 大的数。以原文档配图对应示例[3,2,1,5,6,4], k 2为例堆内维护过程为插入 3 → 插入 2 → 插入 1 时堆大小超过 2弹出堆顶 1 → 插入 5弹出堆顶 2 → 插入 6弹出堆顶 3 → 插入 4弹出堆顶 5最终堆内为[5,6]堆顶 5 即第 2 大元素。复杂度与特点时间复杂度O(n·logk)n 为数组长度。每次push/pop都是 O(logk)总共 n 次。空间复杂度O(k)。与排序相比以 O(k) 的空间换取从 O(nlogn) 到 O(n·logk) 的时间收益当 k 远小于 n 时优势明显且堆可以处理数据流场景数据边到达边处理不需要一次性持有全部数据。Java 实现来自原文档基于PriorityQueueclass KthLargestElementHeap { public int findKthLargest(int[] nums, int k) { PriorityQueueInteger pq new PriorityQueue(); for (int num : nums) { pq.offer(num); if (pq.size() k) { pq.poll(); } } return pq.poll(); } }Python 实现仓库堆专题 thinkings/heap-2.md 中的 Python 风格基于heapqimport heapq class Solution: def findKthLargest(self, nums: List[int], k: int) - int: h [] for num in nums: heapq.heappush(h, num) if len(h) k: heapq.heappop(h) return h[0]补充一点Python 的heapq只提供小顶堆恰好本题就是要小顶堆因此无需像求「第 K 小」那样使用「入堆取反」的方式模拟大顶堆该技巧详见 thinkings/heap-2.md 的「模拟大顶堆」小节。解法三Quick Select平均 O(n)思路Quick Select 类似快排选取 pivot通过 partition 把小于 pivot 的元素移到 pivot 之前这样 pivot 所在的位置就是第 pivot index 小的元素。但不需要完全给数组排序只要判断当前 pivot 的位置是否恰好是第(n-k)小的位置即可——如果是直接返回。具体步骤来自原文档1. 在数组区间随机取 pivot index left random(right-left)。 2. 根据 pivot 做 partition在数组区间内把小于 pivot 的数都移到 pivot 左边。 3. 得到 pivot 的位置 indexcompare(index, (n-k)) a. index n-k - 找到第 k 大元素直接返回结果。 b. index n-k - 答案在 index 右边继续查找数组区间 [index1, right]。 c. index n-k - 答案在 index 左边继续查找数组区间 [left, index-1]。以示例 2 的[3,2,3,1,2,4,5,5,6], k 4为例问题等价于找第n-k 9-4 5小的元素。第一次以 pivot2 对区间 [0,8] 分区得到 pivot 位置后比较随后递归地在包含答案的区间继续分区最终定位到元素 4见下图的分区演进过程。复杂度平均时间复杂度O(n)。每次 partition 后只递归处理一侧规模大致减半总工作量约为n n/2 n/4 ... O(n)。最坏时间复杂度O(n²)。当 pivot 每次都选到极端值如每次都是最大/最小元素时退化为每次只排除一个元素。因此代码中普遍采用随机选取 pivot来避免最坏情况。为什么随机 pivot 很关键原文档给出的 Java 代码中使用了Random random new Random()来随机选择pivotIndex。随机化的意义在于对「基本有序」的输入如果固定取最左端做 pivotQuick Select 会退化为 O(n²)随机选取则让退化概率极低保证平均意义下的 O(n) 表现。Java 实现来自原文档class KthLargestElementQuickSelect { static Random random new Random(); public int findKthLargest3(int[] nums, int k) { int len nums.length; return select(nums, 0, len - 1, len - k); } private int select(int[] nums, int left, int right, int k) { if (left right) return nums[left]; // random select pivotIndex between left and right int pivotIndex left random.nextInt(right - left); // do partition, move smaller than pivot number into pivot left int pos partition(nums, left, right, pivotIndex); if (pos k) { return nums[pos]; } else if (pos k) { return select(nums, left, pos - 1, k); } else { return select(nums, pos 1, right, k); } } private int partition(int[] nums, int left, int right, int pivotIndex) { int pivot nums[pivotIndex]; // move pivot to end swap(nums, right, pivotIndex); int pos left; // move smaller num to pivot left for (int i left; i right; i) { if (nums[i] pivot) { swap(nums, pos, i); } } // move pivot to original place swap(nums, right, pos); return pos; } private void swap(int[] nums, int i, int j) { int tmp nums[i]; nums[i] nums[j]; nums[j] tmp; } }Python 实现自顶向下、更贴近原文档 Java 结构的版本可直接运行import random class Solution: def findKthLargest(self, nums: List[int], k: int) - int: n len(nums) return self.select(nums, 0, n - 1, n - k) def select(self, nums, left, right, k): if left right: return nums[left] pivot_index left random.randint(0, right - left) pos self.partition(nums, left, right, pivot_index) if pos k: return nums[pos] elif pos k: return self.select(nums, left, pos - 1, k) else: return self.select(nums, pos 1, right, k) def partition(self, nums, left, right, pivot_index): pivot nums[pivot_index] # 把 pivot 先挪到区间末尾然后从左到右把小于 pivot 的交换到前面 nums[pivot_index], nums[right] nums[right], nums[pivot_index] pos left for i in range(left, right 1): if nums[i] pivot: nums[pos], nums[i] nums[i], nums[pos] pos 1 nums[right], nums[pos] nums[pos], nums[right] return pos三种解法对比与选型建议解法时间复杂度空间复杂度是否处理数据流适用场景排序O(nlogn)O(logn) 或 O(1)否需一次性持有全部数据代码最简单k 与 n 接近时性价比最高固定小顶堆O(n·logk)O(k)是数据可边到达边入堆k 远小于 n数据流/动态数据场景Quick Select平均 O(n)最坏 O(n²)O(logn)递归栈否追求最优时间、数组可整体修改时选型要点面试中建议从「排序」讲到「堆」再讲到「Quick Select」体现递进式的优化思维若题目强调输入是数据流、无法预知长度堆是唯一合适的选择如 295. 数据流的中位数 用双堆维护本质就是第 K 小/第 K 大问题的变体Quick Select 平均 O(n) 最优但要结合随机 pivot 防退化且会修改原数组partition 是原地交换。关键点分析原文档给出的三条关键结论这里结合仓库专题进一步展开直接排序很简单但 O(nlogn) 并不是最优适合作为第一步的保底解。堆解法的关键是维护一个 K 大小的小顶堆扫描一遍数组最后堆顶元素即是所求它的本质是仓库 thinkings/heap-2.md 的「固定堆」技巧——固定一个大小为 k 的小顶堆可以快速求第 k 大的数。Quick Select 的关键是取 pivot、对数组区间做 partition、比较 pivot 的位置类似二分地取 pivot 左边或右边继续递归查找它属于「减治」只递归一侧而非快排的「分治」两侧都递归这正是其平均 O(n) 的来源。进阶把「固定堆」迁移到同类问题掌握了第 215 题的固定堆套路可以直接迁移到仓库中一系列「第 K 大/第 K 小」题目295. 数据流的中位数用一个大顶堆 一个小顶堆把中位数问题拆解成两个固定堆的堆顶问题378. 有序矩阵中第 K 小的元素原文指出「用大顶堆可以解决时间复杂度 Klogn」但未利用矩阵有序的特性故非最优Kth-Pair-Distance.md求第 K 小的绝对值差既可用固定大顶堆也可用小顶堆弹 K 次get-kth-magic-number-lcci.md使用小顶堆每次取一个、取 K 次即得第 K 个丑数2102. 序列顺序排名跟踪器动态求第 K 大场景原文同样建议使用固定堆技巧。此外仓库 thinkings/binary-search-1.md 还提供了另一条路线对「第 K 大/小」问题二分法同样可解如「计数二分」它与堆解法的区别在于——堆适合动态求极值而二分适合静态解空间上的计数判定二者互为补充。小结「数组中的第 K 个最大元素」是堆与快速选择两大知识体系的经典交汇题一题吃透三解法排序O(nlogn)最直观的保底解固定小顶堆O(n·logk)、O(k) 空间天然支持数据流是「固定堆」技巧的入门题Quick Select平均 O(n)随机 pivot 防退化体现减治思想。原文档在 README.md 中被列为仓库题解目录的组成部分对应题目编号 0215。建议读者按「排序 → 堆 → Quick Select」的顺序亲自实现一遍并对照仓库 thinkings/heap.md 与 thinkings/heap-2.md 的专题内容把固定堆、多路归并等技巧串联起来这样第 K 大/第 K 小一类题目都能举一反三。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考