优先队列（典型算法思想）—— OJ例题算法解析思路

目录

一、1046. 最后一块石头的重量 - 力扣（LeetCode）

算法代码： 

代码思路

使用优先队列（大根堆）

将所有石头放入堆中

模拟碰撞过程

返回最后的重量

代码解析

时间复杂度

示例

输入

输出

二、703. 数据流中的第 K 大元素 - 力扣（LeetCode） 

算法代码： 

代码思路

使用小根堆（最小堆）

构造函数

添加元素的方法

代码解析

时间复杂度

示例

输入

输出

三、692. 前K个高频单词 - 力扣（LeetCode）

算法代码： 

代码思路

统计单词频率

自定义比较器

维护小根堆

提取结果

代码解析

时间复杂度

示例

输入

输出

四、295. 数据流的中位数 - 力扣（LeetCode） 

算法代码： 

代码思路

使用两个堆

添加数字

计算中位数

代码解析

时间复杂度

示例

使用示例

输出

---

一、1046. 最后一块石头的重量 - 力扣（LeetCode）

算法代码： 

class Solution {
public:int lastStoneWeight(vector<int>& stones) {// 1. 创建⼀个⼤根堆priority_queue<int> heap;// 2. 将所有元素丢进这个堆⾥⾯for (auto x : stones)heap.push(x);// 3. 模拟这个过程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;}
};

代码思路

1. 使用优先队列（大根堆）

   • 利用 priority_queue 来模拟石头的碰撞过程。大根堆可以帮助我们快速找到当前最重的两块石头。

2. 将所有石头放入堆中

   • 通过循环将给定的石头重量插入到优先队列中。这样，最重的石头将始终位于堆的顶部。

3. 模拟碰撞过程

   • 使用 while 循环，当堆中石头的数量大于 1 时，继续进行碰撞。

     • 从堆中取出两块最重的石头（a 和 b）。

     • 如果 a 和 b 不相等，将它们的重量差（a - b）重新放回堆中。

     • 如果它们相等，则两块石头都被摧毁，不会被放回堆中。

4. 返回最后的重量

   • 当堆中只剩下一个石头时，返回这个石头的重量；如果没有石头剩下，则返回 0。

代码解析

class Solution {
public:int lastStoneWeight(vector<int>& stones) {// 1. 创建一个大根堆priority_queue<int> heap;// 2. 将所有元素丢进这个堆里面for (auto x : stones)heap.push(x);// 3. 模拟这个过程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; // 返回最后的重量}
};

时间复杂度

• 将所有石头插入到优先队列的时间复杂度是 O(n log n)，其中 n 是石头的数量。

• 每次从堆中取出两个元素并可能插入一个元素的操作时间复杂度是 O(log n)，这在最坏情况下会进行 n 次，因此整体最坏的时间复杂度为 O(n log n)。

示例

输入

vector<int> stones = {2, 7, 4, 1, 8, 1};
Solution sol;
cout << sol.lastStoneWeight(stones); // 输出：1

输出

• 在这个例子中，最终剩下的石头重量是 1。

这种方法通过使用大根堆有效地处理了石头碰撞的问题，能够快速找到最重的石头并进行处理。

二、703. 数据流中的第 K 大元素 - 力扣（LeetCode） 

算法代码： 

class KthLargest {// 创建⼀个⼤⼩为 k 的⼩跟堆priority_queue<int, vector<int>, greater<int>> heap;int _k;public:KthLargest(int k, vector<int>& nums) {_k = k;for (auto x : nums) {heap.push(x);if (heap.size() > _k)heap.pop();}}int add(int val) {heap.push(val);if (heap.size() > _k)heap.pop();return heap.top();}
};
/*** Your KthLargest object will be instantiated and called as such:* KthLargest* obj = new KthLargest(k, nums);* int param_1 = obj->add(val);*/

代码思路

1. 使用小根堆（最小堆）

   • 利用 priority_queue 来创建一个小根堆，堆中最多保留 k 个元素。小根堆的特性是堆顶（即顶部元素）是当前堆中最小的元素。

2. 构造函数

   • KthLargest(int k, vector<int>& nums) 构造函数接受一个整数 k 和一个整数数组 nums。

   • 将数组中的元素依次插入到小根堆中，对于每个插入的元素，如果堆的大小超过 k，则移除堆顶元素（即最小元素）。

   • 这样在堆中始终保持 k 个最大的元素，堆顶元素即为第 k 大的元素。

3. 添加元素的方法

   • int add(int val) 方法用于向数据结构中添加一个新元素 val。

   • 将新元素插入堆中，并再次检查堆的大小。如果堆的大小超过 k，则移除堆顶元素。

   • 返回当前堆顶元素，这个元素就是当前的第 k 大元素。

代码解析

class KthLargest {// 创建一个大小为 k 的小根堆priority_queue<int, vector<int>, greater<int>> heap;int _k;public:KthLargest(int k, vector<int>& nums) {_k = k; // 初始化 kfor (auto x : nums) {heap.push(x); // 将元素插入堆中if (heap.size() > _k) // 如果堆的大小超过 kheap.pop(); // 移除堆顶元素}}int add(int val) {heap.push(val); // 插入新元素if (heap.size() > _k) // 如果堆的大小超过 kheap.pop(); // 移除堆顶元素return heap.top(); // 返回当前的第 k 大元素}
};
/*** Your KthLargest object will be instantiated and called as such:* KthLargest* obj = new KthLargest(k, nums);* int param_1 = obj->add(val);*/

时间复杂度

• 在构造函数中，插入 n 个元素到堆中的时间复杂度为 O(n log k)，因为每次插入堆的操作是 O(log k)。

• 在 add 方法中，每次插入和检索操作的时间复杂度为 O(log k)。

• 整个算法的空间复杂度为 O(k)，因为堆中最多存储 k 个元素。

示例

输入

int k = 3;
vector<int> nums = {4, 5, 8, 2};
KthLargest* obj = new KthLargest(k, nums);
int param_1 = obj->add(3); // 返回 4
int param_2 = obj->add(5); // 返回 5
int param_3 = obj->add(10); // 返回 5
int param_4 = obj->add(9); // 返回 8
int param_5 = obj->add(4); // 返回 8

输出

• param_1 为 4，说明现在的第 3 大元素是 4。

• param_2 为 5，说明现在的第 3 大元素是 5。

• param_3 为 5，依然是第 3 大元素。

• param_4 为 8，说明现在的第 3 大元素是 8。

• param_5 也为 8，依然是第 3 大元素。

这种实现方式通过小根堆高效地维护了动态数组中第 k 大元素的状态，适合于需要频繁添加元素并查询第 k 大元素的场景。

 

三、692. 前K个高频单词 - 力扣（LeetCode）

算法代码： 

class Solution {typedef pair<string, int> PSI;struct cmp {bool operator()(const PSI& a, const PSI& b) {if (a.second == b.second) // 频次相同，字典序按照⼤根堆的⽅式排列{return a.first < b.first;}return a.second > b.second;}};public:vector<string> topKFrequent(vector<string>& words, int k) {// 1. 统计⼀下每⼀个单词的频次unordered_map<string, int> hash;for (auto& s : words)hash[s]++;// 2. 创建⼀个⼤⼩为 k 的堆priority_queue<PSI, vector<PSI>, cmp> heap;// 3. TopK 的主逻辑for (auto& psi : hash) {heap.push(psi);if (heap.size() > k)heap.pop();}// 4. 提取结果vector<string> ret(k);for (int i = k - 1; i >= 0; i--) {ret[i] = heap.top().first;heap.pop();}return ret;}
};

代码思路

1. 统计单词频率

   • 使用 unordered_map<string, int> 来统计每个单词在输入数组中的出现次数。

2. 自定义比较器

   • 定义一个结构体 cmp，用于优先队列中元素的比较。这个比较器实现了以下逻辑：

     • 如果两个单词的频率相同，则按字典序进行排序（按字母逆序，即较大的字母排在前面，形成一个大根堆）。

     • 否则，频率较高的单词应排在前面（形成一个小根堆）。

3. 维护小根堆

   • 使用 priority_queue 来创建一个小根堆，存储单词及其频率。

   • 遍历频率统计的哈希表，将每个单词及其频率插入堆中。如果堆的大小超过 k，则弹出堆顶元素，从而保持堆中只包含 k 个频率最高的单词。

4. 提取结果

   • 创建一个结果向量 ret，用于存储最终的 k 个单词。

   • 由于我们在维护小根堆时，频率最高的单词在堆底，因此提取时需要从堆中依次弹出元素，并逆序填入结果向量。

代码解析

class Solution {typedef pair<string, int> PSI; // 定义一个字符串-频率对struct cmp {bool operator()(const PSI& a, const PSI& b) {if (a.second == b.second) // 如果频率相同，按字典序比较{return a.first < b.first; // 字典序：较大的字母排在前面}return a.second > b.second; // 否则按频率比较}};public:vector<string> topKFrequent(vector<string>& words, int k) {// 1. 统计每一个单词的频次unordered_map<string, int> hash;for (auto& s : words)hash[s]++;// 2. 创建一个大小为 k 的小根堆priority_queue<PSI, vector<PSI>, cmp> heap;// 3. TopK 的主逻辑for (auto& psi : hash) {heap.push(psi); // 插入单词频率对if (heap.size() > k) // 如果堆的大小超过 kheap.pop(); // 移除堆顶元素}// 4. 提取结果vector<string> ret(k); // 结果向量for (int i = k - 1; i >= 0; i--) {ret[i] = heap.top().first; // 获取堆顶元素的单词heap.pop(); // 移除堆顶元素}return ret; // 返回结果}
};

时间复杂度

• 统计频率的时间复杂度为 O(n)，其中 n 是单词数组的长度。

• 在最坏情况下，当哈希表中有 n 个不同单词时，维护小根堆的时间复杂度为 O(n log k)，因为每次插入和删除堆顶的操作都是 O(log k)。

• 因此，整体时间复杂度为 O(n log k)。

示例

输入

vector<string> words = {"i", "love", "leetcode", "i", "love", "coding"};
int k = 2;
Solution sol;
vector<string> result = sol.topKFrequent(words, k); // 返回 {"i", "love"}

输出

• result 包含了出现频率最高的两个单词 “i” 和 "love"。

这种实现方式通过使用哈希表和小根堆有效地解决了查找第 k 个频繁单词的问题，能够快速处理数据并返回结果。

四、295. 数据流的中位数 - 力扣（LeetCode） 

算法代码： 

class MedianFinder {priority_queue<int> left;                             // ⼤根堆priority_queue<int, vector<int>, greater<int>> right; // ⼩根堆
public:MedianFinder() {}void addNum(int num) {// 分类讨论即可if (left.size() == right.size()) // 左右两个堆的元素个数相同{if (left.empty() || num <= left.top()) // 放 left ⾥⾯{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() {if (left.size() == right.size())return (left.top() + right.top()) / 2.0;elsereturn left.top();}
};
/*** Your MedianFinder object will be instantiated and called as such:* MedianFinder* obj = new MedianFinder();* obj->addNum(num);* double param_2 = obj->findMedian();*/

代码思路

1. 使用两个堆

   • 大根堆 (left)：存储较小的一半数字，堆顶是这部分数字的最大值。

   • 小根堆 (right)：存储较大的一半数字，堆顶是这部分数字的最小值。

2. 添加数字

   • 当添加一个新的数字时，根据当前两个堆的大小和新数字的值决定将其放入哪个堆：

     • 如果两个堆的大小相同，且新数字小于等于大根堆的堆顶，则将其放入大根堆；否则，将其放入小根堆，然后将小根堆的堆顶元素移到大根堆中。

     • 如果大根堆的大小大于小根堆，且新数字小于等于大根堆的堆顶，则将其放入大根堆，并将其堆顶元素移到小根堆；否则，直接放入小根堆。

   • 这样可以保证大根堆的元素总是小于等于小根堆的元素，并且大根堆的大小要么等于小根堆的大小，要么大一个元素。

3. 计算中位数

   • 如果两个堆的大小相等，则中位数为两个堆顶元素的平均值。

   • 如果大根堆的大小大于小根堆，则中位数为大根堆的堆顶元素。

 

代码解析

class MedianFinder {priority_queue<int> left;                             // 大根堆priority_queue<int, vector<int>, greater<int>> right; // 小根堆public: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() {if (left.size() == right.size())return (left.top() + right.top()) / 2.0; // 两堆大小相同elsereturn left.top(); // 大根堆较多}
};
/*** Your MedianFinder object will be instantiated and called as such:* MedianFinder* obj = new MedianFinder();* obj->addNum(num);* double param_2 = obj->findMedian();*/

时间复杂度

• addNum 方法的时间复杂度是 O(log n)，因为每次插入堆的时间复杂度为 O(log n)。

• findMedian 方法的时间复杂度是 O(1)，因为只需返回堆顶元素。

• 整体的空间复杂度是 O(n)，存储所有的数字。

示例

使用示例

MedianFinder* obj = new MedianFinder();
obj->addNum(1);
obj->addNum(2);
double median1 = obj->findMedian(); // 返回 1.5
obj->addNum(3);
double median2 = obj->findMedian(); // 返回 2.0

输出

• 第一次调用 findMedian() 时，返回 1.5，因为当前的数字是 1 和 2。

• 第二次调用时，返回 2.0，因为当前的数字是 1、2 和 3。

这种实现方式通过使用两个堆来高效地维护动态数据集的中位数，适用于需要频繁添加数字并查询中位数的场景。