网站模板文件怎么下载,wordpress 资讯插件,wordpress链接数据库文件,建设网站需要那几部文章目录 1. 前言2. 算法题1046.最后一块石头的重量703.数据流中的第K大元素 2.5 如何选择大根堆 与 小根堆#xff1f; 为什么选择大根堆#xff08;小根堆#xff09;#xff1f;692.前K个高频单词295.数据流的中位数 1. 前言
我们知道#xff1a;优先级队列是一种常用… 文章目录 1. 前言2. 算法题1046.最后一块石头的重量703.数据流中的第K大元素 2.5 如何选择大根堆 与 小根堆 为什么选择大根堆小根堆692.前K个高频单词295.数据流的中位数 1. 前言
我们知道优先级队列是一种常用的数据结构用于解决许多算法问题。基于堆Heap实现在每次操作中能够快速找到最大或最小值。
使用优先级队列的典型算法问题包括
Top K 问题查找列表中前 K 个最大或最小的元素。合并 K 个排序数组将 K 个已排序的数组合并为一个有序数组。Dijkstra 算法在加权图中找到从起点到目标节点的最短路径。Huffman 编码使用最小堆构建前缀编码树来压缩数据。
下面会挑选一些算法题并使用优先级队列进行解题。 2. 算法题
1046.最后一块石头的重量 思路
解法大根堆大根堆每个节点都大于等于其子节点则堆顶节点为最大的 将数组中所有元素加入堆中并进行循环直至堆为空循环每次 取两次堆顶元素即当前最重的两石头将两元素差继续入堆重复过程直至循环结束 如果堆中还剩一个元素返回该元素如果已经没有元素返回0
代码
int lastStoneWeight(vectorint stones) {priority_queueint heap; // 创建大根堆// 将数组所有元素添加到堆中for(int stone : stones) heap.push(stone);while(heap.size() 1){// 每次取最大的两个数int a heap.top(); heap.pop();int b heap.top(); heap.pop();if(a b) heap.push(a - b);}return heap.size() ? heap.top() : 0;
}703.数据流中的第K大元素 思路
题意分析根据题目可以看出来该题是一道topK类型题解法全局变量 小根堆 使用全局变量可以省去函数之间传参的过程也方便编写代码 创建全局变量标记k和创建全局小根堆 关于为什么选择小根堆可以看后面的解释。 由于add函数要求添加数字后返回第k大的元素对于构造函数KthLargest我们直接将数组中前k大的元素插入对于add函数直接将val插入到堆中并判断是否堆内元素超出k个 如果超出则pop掉后直接返回堆顶元素即为第K大
2.5 如何选择大根堆 与 小根堆 为什么选择大根堆小根堆 代码
class KthLargest {
public:// 小根堆priority_queueint, vectorint, greaterint heap;int _k;KthLargest(int k, vectorint nums) {_k k;for(int num : nums){heap.push(num);if(heap.size() _k) heap.pop();} }int add(int val) {heap.push(val);if(heap.size() _k) heap.pop();return heap.top();}
};692.前K个高频单词 思路
题意分析即返回数组中出现次数最多的字符串单词解法哈希表 优先级队列 哈希表统计每个单词的出现次数根据题目要求当单词的频率相同时按照字典序排列则我们自定义优先级队列的比较函数。则 当单词频率不同时用小堆的比较方式当单词频率相同时按照字典序用大堆的比较方式 将哈希表中统计的前k高的 字母以及频率 加入到队列最后返回结果遍历堆每次加入到结果集result中并pop即可。
代码
vectorstring topKFrequent(vectorstring words, int k) {// 统计单词出现频率unordered_mapstring, int freq;for (const string word : words) {freq[word];}// 自定义优先队列的比较函数auto cmp [](const pairstring, int a, const pairstring, int b) {// 比较出现次数如果相同则按照字母顺序return a.second b.second || (a.second b.second a.first b.first);};// 优先队列默认是大顶堆用于存储频率最高的 k 个单词priority_queuepairstring, int, vectorpairstring, int, decltype(cmp) pq(cmp);// 遍历统计好的频率将单词加入优先队列for (const auto entry : freq) {pq.push(entry);if (pq.size() k) {pq.pop(); // 如果队列大小超过 k则弹出频率最小的单词}}// 从优先队列中取出结果vectorstring result(k);for (int i k - 1; i 0; --i) {result[i] pq.top().first; // 逆序存储结果pq.pop();}return result;
}295.数据流的中位数 思路 题意分析题目要求实现一个类类中包含一个构造函数、一个add函数用于添加元素、以及一个find函数 解法一排序 sort 对于本题使用该排序法是会超时的 解法二插入排序的思想 插入排序思想解本题是有可能超时的但依然需要了解这种解题思想。 解法三大小堆维护 上图解释了方法思路具体细节看下面代码即可。
代码
class MedianFinder {
public:// 大小堆左大堆右小堆// 且当共有奇数个元素时左存多一个元素priority_queueint, vectorint left;priority_queueint, vectorint, greaterint right;MedianFinder() {} // 构造void addNum(int num) {if(left.size() right.size()){ if(left.empty() || num left.top()){left.push(num);}else{right.push(num);left.push(right.top());right.pop();}}else{if(num left.top()){left.push(num);right.push(left.top());left.pop();}else{right.push(num);}}}double findMedian() {return (left.size() right.size()) ? (left.top() right.top()) / 2.0 : left.top();}
};
