LeetCode Hot 100 —— 堆

堆的概念堆heap是一种特殊的完全二叉树常用来快速找到“最大值”或“最小值”。堆分两种大顶堆每个父节点都 它的子节点所以根节点一定是最大值小顶堆每个父节点都 它的子节点所以根节点一定是最小值215. 数组中的第K个最大元素基于快速排序的选择方法思路和算法可以用快速排序来解决这个问题先对原数组排序再返回倒数第 k 个位置这样平均时间复杂度是O(nlogn)但其实我们可以做的更快。首先我们来回顾一下快速排序是一种高效、常用、分治法的排序算法。我们对数组a[l⋯r]做快速排序的过程是分解选一个基准数将数组 a[l⋯r]「划分」成两个子数组 a[l⋯q−1]、a[q1⋯r]使得 a[l⋯q−1] 中的每个元素小于等于 a[q]且 a[q] 小于等于 a[q1⋯r] 中的每个元素。其中计算下标 q 也是「划分」过程的一部分。解决通过递归调用快速排序再对左右两边的子数组 a[l⋯q−1] 和 a[q1⋯r] 进行递归排序。合并因为子数组都是原址排序的所以不需要进行合并操作a[l⋯r] 已经有序。上文中提到的划分过程是从子数组 a[l⋯r] 中选择任意一个元素 x 作为主元调整子数组的元素使得左边的元素都小于等于它右边的元素都大于等于它。由此可以发现每次经过「划分」操作后我们一定可以确定一个元素的最终位置即 x 的最终位置为 q并且保证 a[l⋯q−1] 中的每个元素小于等于 a[q]且 a[q] 小于等于 a[q1⋯r] 中的每个元素。所以只要某次划分的 q 为倒数第 k 个下标的时候我们就已经找到了答案。因此我们可以改进快速排序算法来解决这个问题在分解的过程当中我们会对子数组进行划分如果划分得到的 q 正好就是我们需要的下标就直接返回 a[q]否则如果 q 比目标下标小就递归右子区间否则递归左子区间。这样就可以把原来递归两个区间变成只递归一个区间提高了时间效率。这就是快速选择算法。我们知道快速排序的性能和划分出的子数组的长度密切相关。直观地理解如果每次规模为 n 的问题我们都划分成 1 和 n−1每次递归的时候又向 n−1 的集合中递归这种情况是最坏的时间代价是 O(n^2)。我们可以引入随机化来加速这个过程它的时间代价的期望是 O(n)。需要注意的是这个时间复杂度只有在随机数据下才成立而对于精心构造的数据则可能表现不佳。因此我们这里并没有真正地使用随机数而是使用双指针的方法这种方法能够较好地应对各种数据。思路简练地概括成这样递归三部曲1、确定递归函数的参数和返回值快速排序核心函数int quickselect(vectorint nums, int l, int r, int k)参数含义nums原数组l当前查找区间左边界r当前查找区间右边界k目标下标所以返回值直接是nums[k]2、确定终止条件if(lr)returnnums[k];如果当前区间只剩下一个元素那这个元素就是答案。3、确定单层递归的逻辑核心代码classSolution{public:intquickSelect(vectorintnums,intl,intr,intk){if(lr){returnnums[k];}intil;//左指针指向左边界intjr;//右指针指向右边界intpivotnums[(lr)/2];//先取要判断的元素为中值while(ij){while(nums[i]pivot)i;while(nums[j]pivot)j--;//此时左右指针都指向了第一个不满足顺序的元素if(ij){swap(nums[i],nums[j]);i;j--;}}// 循环结束后[l, j] 中的元素 pivot, [i, r] 中的元素 pivot重要// 中间可能有一段元素 pivot//循环结束时, j是左半边最后一个元素的位置, i是右半边第一个元素的位置if(kj)returnquickSelect(nums,l,j,k);if(ki)returnquickSelect(nums,i,r,k);returnnums[k];//k落在中间等于 pivot 的区域注意这里k是指索引为k的元素}intfindKthLargest(vectorintnums,intk){intnnums.size();returnquickSelect(nums,0,n-1,n-k);//注意第k大是n-k}};【注】1、循环结束后[l, j] 中的元素 pivot, [i, r] 中的元素 pivot重要2、int quickSelect(vectorint nums, int l, int r, int k)这里k是索引为k的元素quickSelect函数是找到索引为k的元素而题目要求是找到第k大所以是n-kquickSelect(nums,0,n-1,n-k);由于要找到第k大所以是n-k法二用堆来做classSolution{public:intfindKthLargest(vectorintnums,intk){// 使用大顶堆存储所有元素priority_queueintheap;//默认是大顶堆// 将数组元素加入大根堆for(intnum:nums){heap.push(num);}// 弹出前 k - 1 大的元素for(inti1;ik;i){heap.pop();}// 堆顶元素就是第 k 大的元素returnheap.top();}};ACM#includeiostream#includevector#includealgorithmusingnamespacestd;classSolution{public:intquickSelect(vectorintnums,intl,intr,intk){if(lr){returnnums[k];}intil;//左指针指向左边界intjr;//右指针指向右边界intpivotnums[(lr)/2];//先取要判断的元素为中值while(ij){while(nums[i]pivot)i;while(nums[j]pivot)j--;//此时左右指针都指向了第一个不满足顺序的元素if(ij){swap(nums[i],nums[j]);i;j--;}}// 循环结束后[l, j] 中的元素 pivot, [i, r] 中的元素 pivot// 中间可能有一段元素 pivot//循环结束时, j是左半边最后一个元素的位置, i是右半边第一个元素的位置if(kj)returnquickSelect(nums,l,j,k);if(ki)returnquickSelect(nums,i,r,k);returnnums[k];//k落在中间等于 pivot 的区域}intfindKthLargest(vectorintnums,intk){intnnums.size();returnquickSelect(nums,0,n-1,n-k);}};intmain(){intn,k;cinnk;vectorintnums(n);for(inti0;in;i)cinnums[i];Solution solution;coutsolution.findKthLargest(nums,k)endl;return0;}347. 前k个高频元素首先统计元素出现的频率这一类的问题可以使用map来进行统计key存放元素value存放元素出现次数。没有必要对所有元素进行排序只需要维护k个有序的集合就可以了因为求频率前k高的。选用大顶堆和小顶堆来实现。大顶堆和小顶堆是堆Heap这种数据结构的两种主要形式。它们都是特殊的完全二叉树但在节点的排序方式上刚好相反。大顶堆中根节点堆顶是整个堆中最大的元素。从堆顶往下路径上的元素是递减的非严格递减。小顶堆中根节点堆顶是整个堆中最小的元素。从堆顶往下路径上的元素是递增的非严格递增。注意大顶堆的应用维护前 k 个最小元素因为pop出的是根节点是最大的小顶堆的应用维护前 k 个最大元素所以这里用小顶堆。对频率进行排序这里我们可以使用一种容器适配器就是优先级队列(priority_queue)。什么是优先级队列呢其实就是一个披着队列外衣的堆因为优先级队列对外接口只是从队头取元素从队尾添加元素再无其他取元素的方式看起来就是一个队列。而且优先级队列内部元素是自动依照元素的权值排列。那么它是如何有序排列的呢大顶堆、小顶堆是实现优先级队列的常用底层结构。缺省情况下priority_queue利用max-heap大顶堆完成对元素的排序这个大顶堆是以vector为表现形式的complete binary tree完全二叉树。所以大家经常说的大顶堆堆头是最大元素小顶堆堆头是最小元素如果懒得自己实现的话就直接用priority_queue优先级队列就可以了底层实现都是一样的。代码思路先使用unordered_map统计每个数字出现的频率。然后利用小顶堆维护频率最高的 K 个元素。一、priority_queuepairint, int, vectorpairint, int, mycomparison pri_que;priority_queue 本质上是一个类模板。C中需要做到“同一套逻辑能装任意类型并且还能自定义排序规则/底层容器”。要达到这个“泛型”最直接的机制就是类模板。可以理解为priority_queue不是一个具体类名而是一个“类的生成器”。你给它模板参数它才变成某个具体类型的队列。例如priority_queueinta;priority_queuepairint,int,vectorpairint,int,mycomparisonb;priority_queueint a;后两个参数用默认值。1、T元素类型pairint, int队列里每个元素长这样{key, freq}你代码里是 {数字, 出现次数}2、Container底层容器类型vectorpairint, intpriority_queue 内部实际是用一个 vector 来存数据然后用堆算法维护顺序这里就是“用 vector 存 pair”3、Compare比较器类型mycomparison类在类里重载()决定“谁应该在堆顶”的规则因为默认情况下priority_queue利用max-heap大顶堆完成对元素的排序所以要重载。你写的 operator() 让它按 second频率比较从而实现按频率排序的小顶堆。为何重载就实现了重新定义比较逻辑因为priority_queue 内部会保存一个 Compare comp;并在调整堆push/pop时反复调用comp(x, y)来决定谁该在上面。整体思路自定义小顶堆排序规则定义一个class重载—— 使用unordered_map统计——使用小顶堆排序——收集结果classSolution{public:// 小顶堆classmycomparison{public:booloperator()(constpairint,intlhs,constpairint,intrhs){returnlhs.secondrhs.second;//比较unordered_map中的第二个参数即值}};vectorinttopKFrequent(vectorintnums,intk){// 要统计元素出现频率unordered_mapint,intmap;// mapnums[i],对应出现的次数for(inti0;inums.size();i){map[nums[i]];}// 对频率排序// 定义一个小顶堆大小为kpriority_queuepairint,int,vectorpairint,int,mycomparisonpri_que;// 用固定大小为k的小顶堆扫描所有频率的数值for(autoitmap.begin();it!map.end();it){pri_que.push(*it);if(pri_que.size()k){// 如果堆的大小大于k了则队列弹出保证堆的大小一直为kpri_que.pop();//排序规则在bool operator()里定义了}}// 找出前K个高频元素因为小顶堆先弹出的是k个高频元素中最小的所以倒序来输出到数组vectorintresult(k);for(intik-1;i0;i--){result[i]pri_que.top().first;pri_que.pop();}returnresult;}};【注】0、lhs 参数是一个 pair 对象的引用所以访问成员要用 . 而 - 只能用在指针/迭代器上。1、重载()时const T 是最标准、最安全的写法希望比较过程是纯比较不改数据。2、比较运算在建堆时是如何应用的为什么左大于右就会建立小顶堆反而建立大顶堆在 priority_queue/堆算法里Compare 不是“谁更大谁优先”而是“a 是否应该排在 b 前面a 的优先级是否更低/更靠后”的规则。堆算法维持的是父节点不能“ ”子节点comp less→ 父不能小于子 → 大顶堆comp greater→ 父不能大于子 → 小顶堆3、map[nums[i]]意思是用 nums[i] 当key去查 unordered_map 里对应的 value并返回这个 value 的“引用”可以修改。4、unordered_mapint,int你告诉它key类型、value类型即可pair是它内部自动组合的。priority_queuepairint,int你需要明确告诉它每个元素长什么样而你要“两个值一起存”所以元素类型就得是 pair。5、pri_que.push(*it);it 是unordered_mapint,int::iterator解引用 *it 得到的是一条“键值对”*it 的类型是std::pairconst int, intfirstkey数字是const intmap的key不能被改secondvalue次数是int更直观写法pri_que.push({it-first, it-second});7、priority_queue常用操作函数push(x)插入元素top()取堆顶元素不删除pop()删除堆顶元素size()元素个数empty()是否为空8、vectorint result(k);后面是按下标直接赋值所以(k)是必须的9、for (int i k - 1; i 0; i--) {i 0别忘了ACM:#includeiostream#includequeue#includevector#includeunordered_mapusingnamespacestd;classComparison{public:booloperator()(constpairint,inta,constpairint,intb){returna.secondb.second;}};vectorintFindK(vectorintvec,intk){unordered_mapint,intmap;for(inti0;ivec.size();i){map[vec[i]];}priority_queuepairint,int,vectorpairint,int,Comparisonque;for(autoitmap.begin();it!map.end();it){que.push(*it);if(que.size()k){que.pop();}}vectorintres(k);for(inti0;ik;i){res[i]que.top().first;que.pop();}returnres;}intmain(){intn,k;cinnk;vectorintnums(n);for(inti0;in;i){cinnums[i];}vectorintresFindK(nums,k);for(inti0;ik;i){coutres[i];if(i!k-1)cout ;}coutendl;return0;}295. 数据流的中位数它的核心思想是用两个堆维护两半数据① 定义大小顶堆left大顶堆存较小的一半堆顶是这半里最大的最大的要push出去到右边所以用大顶堆right小顶堆存较大的一半堆顶是这半里最小的②addNum:添加元素时先放入大顶堆再将大顶堆堆顶移动到小顶堆如果小顶堆right元素比大顶堆left多则从小顶堆弹出一个最小元素到大顶堆确保平衡。③findMedian:这样中位数就很好取如果总数是奇数中位数就是 left.top()如果总数是偶数中位数就是 left.top() 和 right.top() 的平均值核心代码classMedianFinder{public:priority_queueintleft;//默认大顶堆priority_queueint,vectorint,greaterintright;MedianFinder(){}voidaddNum(intnum){left.push(num);intresleft.top();right.push(res);left.pop();if(right.size()left.size()){left.push(right.top());right.pop();}}doublefindMedian(){if(left.size()right.size())returnleft.top();return(left.top()right.top())/2.0;}};【注】1、return (left.top( )right.top( ))/2.0;注意/2.0 因为要保留一位小数2、priority_queueint, vectorint, greaterint right;注意第一个是int不是intACM#includevector#includequeue#includeiostream#includestring#includeiomanipusingnamespacestd;classMedianFinder{public:priority_queueintleft;//默认大顶堆priority_queueint,vectorint,greaterintright;MedianFinder(){}voidaddNum(intnum){left.push(num);intresleft.top();right.push(res);left.pop();if(right.size()left.size()){left.push(right.top());right.pop();}}doublefindMedian(){if(left.size()right.size())returnleft.top();return(left.top()right.top())/2.0;}};intmain(){intq;cinq;MedianFinder mf;while(q--){string s;cins;if(sadd){intx;cinx;mf.addNum(x);}elseif(smedian){coutfixedsetprecision(1)mf.findMedian()endl;}}return0;}【注】1、cout fixed setprecision(1) mf.findMedian() endl;固定保留1 位小数要包含头文件#include iomanipfixed表示用普通小数形式输出而不是科学计数法。setprecision(1)表示保留 1 位小数。