巧用小顶堆求解第 K 大元素两道经典题一通百通✨Bilibili 同步视频一、前言二、核心思路剖析2.1 逻辑推演2.2 文字图示演示Plain Text初始状态空堆设定 K 3步骤 1依次压入前 3 个元素 [9, 7, 8]堆满size 3步骤 2新增元素 10入堆后堆 size 4 K3步骤 3新增元素 6入堆后堆 size 4 K3三、复杂度分析⚙️四、C 代码实现4.1 解法一数组中的第 K 大元素4.2 解法二数据流中的第 K 大元素代码解读五、总结与刷题建议 标签# 算法 #堆结构 #C #面试题 #数据结构Bilibili 同步视频巧用小顶堆求解第 K 大元素两道经典题一通百通✨一、前言在算法刷题与面试场景中求解数组 / 数据流中的第 K 大元素是一道出镜率极高的经典题型。不少初学者面对该问题时常会陷入全量排序、暴力遍历的低效思路中。实则借助小顶堆这一精巧的数据结构便可化繁为简、四两拨千斤。本文将由浅入深拆解解题逻辑、推演执行流程、附上完整 C 代码并辅以图文演示原理带你彻底吃透这两道同源考题。二、核心思路剖析世间算法万变不离其宗。两道看似独立的题目 ——数据流中的第 K 大元素与数组中的第 K 大元素内核逻辑高度趋同皆可依托小顶堆实现高效求解。2.1 逻辑推演设我们需要筛选出一组数据里排名前K KK的大数若某元素想要跻身前 K 大序列其数值必须大于当前前 K 个元素里的最小值一旦新元素达标便淘汰原有 K 个元素中的最小值完成一轮更新迭代为了实时、快速获取当前 K 个元素的最小值小顶堆便是最优选择。小顶堆特性堆顶永远是整个堆结构中的最小值查询、弹出堆顶元素的时间复杂度极低。 总结要义以容量为 K 的小顶堆维护全局前 K 大元素堆内留存当前筛选出的 K 个大数堆顶即为整组数据的第 K 大元素。谁数值更小便被优先移出堆外恰似择优留强、汰弱留庸。2.2 文字图示演示Plain Text初始状态空堆设定 K 3堆结构[ 空 ] 目标筛选前3大元素最终堆顶为第3大元素步骤 1依次压入前 3 个元素 [9, 7, 8]堆满size 3小顶堆自动调整结构堆顶为最小值77 ← 堆顶当前前3大最小值 / 9 8 堆内元素{7,9,8}步骤 2新增元素 10入堆后堆 size 4 K3堆顶最小值7被弹出重新调整堆结构新堆顶为88 ← 新堆顶 / 9 10 堆内元素{8,9,10}步骤 3新增元素 6入堆后堆 size 4 K3堆顶最小值6被弹出堆结构不变8 ← 堆顶最终第3大元素 / 9 10全程可见无论元素如何新增更替堆内始终保留当前前 K 大元素堆顶就是我们所求的第 K 大元素。三、复杂度分析⚙️设数据总个数为n nn限定堆容量为K KK时间复杂度每个元素入堆、堆调整操作耗时O ( l o g K ) O(log K)O(logK)整体总复杂度为O ( n l o g K ) O(nlog K)O(nlogK)对比全量排序O ( n l o g n ) O(nlog n)O(nlogn)当K l l n K ll nKlln时效率提升十分显著。空间复杂度仅开辟大小为K KK的堆空间复杂度为O ( K ) O(K)O(K)内存占用极小。四、C 代码实现C 标准库中默认优先队列priority_queue为大顶堆我们可通过仿函数greaterint改造为小顶堆适配本题需求。4.1 解法一数组中的第 K 大元素适用于一次性给定完整数组直接求解第 K 大元素场景。#includeiostream#includevector#includequeue// 优先队列堆头文件usingnamespacestd;// 查找数组中第 K 大元素intfindKthLargest(vectorintnums,intk){// 定义小顶堆priority_queue数据类型, 底层容器, 比较规则priority_queueint,vectorint,greaterintminHeap;// 遍历所有元素逐个入堆for(intnum:nums){minHeap.push(num);// 堆容量超过 K弹出堆顶最小值if(minHeap.size()k){minHeap.pop();}}// 最终堆顶即为第 K 大元素returnminHeap.top();}intmain(){vectorintarr{3,2,1,5,6,4};intk2;intresfindKthLargest(arr,k);cout数组中第k大元素为resendl;return0;}4.2 解法二数据流中的第 K 大元素适用于动态持续流入数据的场景支持不断添加新数值实时查询第 K 大元素。#includeiostream#includevector#includequeueusingnamespacestd;classKthLargest{private:intk;// 小顶堆维护前 K 大元素priority_queueint,vectorint,greaterintminHeap;public:// 构造函数初始化 K 值与初始数据流KthLargest(intk_val,vectorintnums){kk_val;for(intnum:nums){minHeap.push(num);if(minHeap.size()k){minHeap.pop();}}}// 新增数据流元素并返回当前第 K 大元素intadd(intval){minHeap.push(val);if(minHeap.size()k){minHeap.pop();}returnminHeap.top();}};intmain(){vectorintstream{4,5,8,2};intk3;KthLargestkthLargest(k,stream);// 动态添加元素并输出结果coutkthLargest.add(3)endl;coutkthLargest.add(5)endl;coutkthLargest.add(10)endl;return0;}代码解读priority_queueint, vectorint, greaterint第三参数greaterint是构建小顶堆的核心堆顶始终为最小值元素入堆后强制校验堆大小一旦超出K KK立即弹出堆顶最小值保证堆内永远只留存前 K 大元素数据流版本将逻辑封装为类构造函数初始化初始数据add方法响应动态新增数据贴合真实业务场景。五、总结与刷题建议纵观两道同源题型小顶堆 固定容量 K是贯穿始终的核心解法思路一脉相承以小顶堆作 “筛选容器”守 K 位、汰小值堆顶定论答案。此思路摒弃了全量排序的冗余操作时空表现俱佳也是面试中面试官尤为青睐的解法。✅ 刷题建议先理解堆的底层特性分清大顶堆、小顶堆的使用场景亲手调试上述两份代码观察堆内元素变化对照前文图示加深理解前往力扣平台找到对应原题独立编写代码巩固思路做到提笔即写、思路通透。算法学习非一日之功吃透一类题型、掌握一种思想便可举一反三从容应对同类变式考题。
