教程【免费下载链接】InterviewGuide「InterviewGuide」是阿秀从校园-职场多年计算机自学过程的记录以及学弟学妹们计算机校招秋招经验总结文章的汇总包括但不限于C/C 、Golang、JavaScript、Vue、操作系统、数据结构、计算机网络、MySQL、Redis等学习总结坚持学习持续成长项目地址https://gitcode.com/gh_mirrors/in/InterviewGuide点击查看免费下载从「最小的K个数」看懂 Top K 问题的堆解法「最小的K个数」是《剑指Offer》第 29 题牛客网剑指 Offer 专题也是校招、社招面试中最高频的 Top K 类题目之一。本题输入 n 个整数与参数 K要求找出其中最小的 K 个数例如输入4,5,1,6,2,7,3,8这 8 个数字K 4 时最小 4 个数字为1,2,3,4。读完后你将掌握堆 / 优先队列在 Top K 问题上的经典套路、大顶堆与小顶堆的选择逻辑以及基于 partition 的快选思路和基于快速排序的排序解法并能把这些方法迁移到「第 K 大 / 第 K 小」「前 K 高频」等同源题目上。一、题目描述与示例题目描述输入 n 个整数找出其中最小的 K 个数。例如输入4,5,1,6,2,7,3,8这 8 个数字则最小的 4 个数字是1,2,3,4。示例 1输入 [4,5,1,6,2,7,3,8],4 返回值 [1,2,3,4]说明本题来自牛客网剑指 Offer 专题专栏 导读 中说明该系列共 67 题题目顺序与牛客网保持一致原题出自《何海涛. 剑指 Offer[M]. 电子工业出版社, 2012.》适合校招、社招工作党以及转行计算机的 C 技术栈人士复习使用。二、解法一优先队列最小堆一锤定音原题给出的标准解法是借助 C STL 的priority_queue实现最小堆把全部元素入堆堆顶永远是最小值连续弹出 K 次堆顶即为答案。vectorint GetLeastNumbers_Solution(vectorint input, int k) { if (k input.size()) return vectorint(); priority_queueint, vectorint, greaterint pq; for (auto a : input) pq.push(a); vectorint result; while (k--) { result.push_back(pq.top()); pq.pop(); } return result; }代码要点priority_queueint, vectorint, greaterint声明了一个最小堆小顶堆top()返回堆中最小的元素边界处理当k input.size()时直接返回空vectorint()while (k--)逐次取出堆顶并弹出K 次后 result 中即为从小到大排列的最小的 K 个数。复杂度每个元素入堆 O(log n)n 个元素建堆 O(n log n)弹出 K 个堆顶 O(K log n)。总时间复杂度 O((n K) log n)空间复杂度 O(n)。注意此写法把 n 个元素全部装入堆中堆的规模是 O(n)。面试中这道题更常被追问的是「数据量很大、内存放不下」的变体此时需要改用「只保留 K 个元素」的堆见下一节。三、解法二维护大小为 K 的「大顶堆」空间与效率双优很多同学容易把方向搞反求最小的 K 个数应该用大顶堆less。因为我们要保留的是「当前最小的 K 个候选」堆顶是这 K 个候选里最大的那个每当来了一个比堆顶更小的数就替换堆顶保证堆里永远是最小的 K 个数。原题标题下方也明确标注了该思路的核心声明priority_queueint, vectorint, lessint思路与实现在标准做法基础上优化为只维护 K 个元素的堆vectorint GetLeastNumbers_Solution(vectorint input, int k) { if (k 0 || k input.size()) return vectorint(); priority_queueint maxHeap; // 默认less即大顶堆 for (int a : input) { if (maxHeap.size() k) { maxHeap.push(a); // 堆未满直接放入 } else if (a maxHeap.top()) { maxHeap.pop(); // 来了更小的数替换堆顶 maxHeap.push(a); } } vectorint result; while (!maxHeap.empty()) { result.push_back(maxHeap.top()); maxHeap.pop(); } return result; }为什么这里用大顶堆堆中只保留 K 个元素堆顶maxHeap.top()是这 K 个中最小的 K 个数里的最大值即「门槛」新元素比门槛小才替换比门槛大直接丢弃这样堆中始终是已扫描元素里最小的 K 个最后堆顶到堆底依次为最小的 K 个数。复杂度每个元素最多一次入堆、一次出堆单次操作 O(log K)总时间复杂度 O(n log K)空间复杂度从 O(n) 降为O(K)。这正是海量数据 Top K 的标准解法在 高频算法笔记的 Top K 问题一节 中给出的口诀同样是「求最大的数用最小堆求最小的数用最大堆」并指出 C 中的最大最小堆要用标准库的priority_queue来实现。四、解法三基于 partition 的 Quick Select快选如果题目只要求返回第 K 小的数或最小的 K 个数还可以用 Quick Select它脱胎于快速排序每次按枢轴 pivot 划分数组小于 pivot 的放左边、大于 pivot 的放右边然后只对包含答案的那一侧递归处理。与快排最大的区别是快排划分后对左右两边都继续排序而快选每次只处理左半边或右半边。以寻找第 K 大的元素为例本仓库高频算法笔记中的 Quick Select 实现// 此为Java实现 public int findKthLargest(int[] nums, int k) { return quickSelect(nums, k, 0, nums.length - 1); } // quick select to find the kth-largest element public int quickSelect(int[] arr, int k, int left, int right) { if (left right) return arr[right]; int index partition(arr, left, right); if (index - left 1 k) return quickSelect(arr, k, left, index - 1); else if (index - left 1 k) return arr[index]; else return quickSelect(arr, k - (index - left 1), index 1, right); }思路要点笔记原文选取一个枢轴 pivot将数组中小于 pivot 的数放左边大于 pivot 的数放右边若左边元素个数 K第 K 大的数在左边数组继续对左边执行相同操作若左边元素个数 K - 1则第 K 大的数就是 pivot若左边元素个数 K第 K 大的数在右边数组对右边执行相同操作。时间复杂度平均 O(n)最坏 O(n²)且不依赖额外堆空间。五、解法四直接排序代码最简把整个数组排序后取前 K 个即可思路最直白适合在代码量最小、面试时间紧张的场景下快速给出答案vectorint GetLeastNumbers_Solution(vectorint input, int k) { if (k input.size()) return vectorint(); sort(input.begin(), input.end()); return vectorint(input.begin(), input.begin() k); }使用sort排序时间复杂度 O(n log n)通过迭代器区间构造返回 vector无需手写循环该解法的缺点在于排序做了大量与 K 无关的多余工作当 n 很大而 K 很小时不如「大小为 K 的堆」高效。该解法未在原题文档中直接给出但仓库 高频算法笔记 Top K 一节 明确将「使用排序方法排序后再寻找 Top K 元素」列为解决 Top K 问题的若干方法之一。六、同源扩展把「最小的 K 个数」迁移到第 K 大与 Top K 高频掌握了堆的方向选择同源题目几乎可以直接套模板。1、215. 数组中的第 K 个最大元素小顶堆维护 K 个元素仓库 LeetCode 215 题解 用的是小顶堆 只保留 K 个元素的思路求第 K 大用最小堆堆里始终是已扫描元素中最大的 K 个堆顶即第 K 大int findKthLargest(vectorint nums, int k) { priority_queueint, vectorint, greaterint res; for (auto a : nums) { res.push(a); if (res.size() k) res.pop(); } return res.top(); }2、347. 前 K 个高频元素哈希计数 小根堆仓库 LeetCode 347 题解 先哈希统计频率再用自定义比较器的小根堆保留频率最高的 K 个元素struct compare { bool operator()(const pairint, int a, const pairint, int b) { return a.second b.second; // 按频率建小根堆 } }; vectorint topKFrequent(vectorint nums, int k) { vectorint ret; unordered_mapint, int hash; for (auto a : nums) hash[a]; priority_queuepairint, int, vectorpairint, int, compare freq; for (auto a : hash) { freq.push(a); if (freq.size() k) freq.pop(); } while (!freq.empty()) { ret.push_back(freq.top().first); freq.pop(); } return ret; }该题解笔记中还特别强调了一句面试黄金提示「求前 k 大用小根堆求前 k 小用大根堆。面试的时候如果说反了会挂」与本题大顶堆解法完全一致。七、数据流场景与堆的更多应用同样是「大顶堆 小顶堆」的组合仓库 剑指 Offer 63 题解数据流中的中位数 展示了堆在流式数据中的经典用法用一个大顶堆保存左半边、一个小顶堆保存右半边保证「左边 右边」且两边元素个数相差不超过 1中位数即为堆顶元素priority_queueint, vectorint, lessint big_heap; // 左边一个大顶堆 priority_queueint, vectorint, greaterint small_heap; // 右边一个小顶堆其核心维护规则笔记原文为数据是偶数时insert 的数据进入「右边最小堆」若插入数字大于 leftMax 直接插入否则先把 cur 插入大顶堆、再把 leftMax 转入小顶堆保证左边 右边数据是奇数时insert 的数据进入「左边最大堆」若插入数字小于 rightMin 直接插入否则先把 cur 插入小顶堆、再把 rightMin 转入大顶堆同样保证左边 右边偶数个元素时中位数mid (leftMax rightMin) / 2奇数个元素时中位数就是leftMax。这道题与「最小的 K 个数」共同构成了「堆解决 Top K / 流式统计」的完整知识闭环值得放在一起记忆。八、复杂度与选型对比小结解法核心数据结构时间复杂度空间复杂度适用场景全量最小堆priority_queueint, vectorint, greaterintO((n K) log n)O(n)n 较小代码最直观大小为 K 的大顶堆priority_queueint默认 lessO(n log K)O(K)n 很大、K 很小海量数据Quick Selectpartition 划分平均 O(n)O(1)原地只需第 K 小 / 第 K 大直接排序sortO(n log n)O(1)原地需要有序结果代码最简面试应答建议先答出全量最小堆的标准解再主动补上「大小为 K 的大顶堆」优化说明海量数据下空间 O(K) 的优势若面试官追问更优时间复杂度再补充 Quick Select。三个层次递进正是本题在 剑指 Offer 系列 67 题 中的考察重点。参考与延伸阅读本题原解与完整系列剑指 Offer 全集第 29 题小节与 29-剑指offer.md 内容一致Top K 问题系统总结高频算法题笔记 · Top K 问题同源 LeetCode 题解215. 数组中的第K个最大元素、347. 前K个高频元素堆的另一经典应用剑指 Offer 63 · 数据流中的中位数数据结构基础堆排序实现高频算法题笔记 · 堆排序赞分享教程【免费下载链接】InterviewGuide「InterviewGuide」是阿秀从校园-职场多年计算机自学过程的记录以及学弟学妹们计算机校招秋招经验总结文章的汇总包括但不限于C/C 、Golang、JavaScript、Vue、操作系统、数据结构、计算机网络、MySQL、Redis等学习总结坚持学习持续成长项目地址https://gitcode.com/gh_mirrors/in/InterviewGuide点击查看免费下载相关推荐CS-Notes 剑指 Offer 题解「最小的 K 个数」两种经典解法——大顶堆与快速选择CS Notes 剑指 Offer 题解「最小的 K 个数」两种经典解法——大顶堆与快速选择 本篇基于 CS Notes 仓库中《剑指 Offer 题解》的知识库文档教程深度解析如何掌握SMU Debug Tool释放AMD Ryzen处理器的隐藏性能深度解析如何掌握SMU Debug Tool释放AMD Ryzen处理器的隐藏性能 想要完全掌控AMD Ryzen处理器的性能潜力吗SMU Debug To教程文档示例工程教育LeetCode 295 数据流的中位数双堆大顶堆 小顶堆解法全解析LeetCode 295 数据流的中位数双堆大顶堆 小顶堆解法全解析 导读 本文以 problems/295.find median from dat文档教程知识库上一篇MuJoCo Python 绑定包详解安装方式、底层加载机制、渲染上下文子包与源码构建下一篇Vue.js 源码分析动态节点标记与 patch 优化创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考