目录
1、 1046. 最后一块石头的重量
2、 703. 数据流中的第 K 大元素
为什么小根堆可以解决TopK问题？
3、 692. 前K个高频单词
4、 295. 数据流的中位数
1、 1046. 最后一块石头的重量
思路：根据示例发现可以用大根堆(降序)模拟这个过程。
class Solution {
public:
int lastStoneWeight(vector<int>& stones) {
priority_queue<int> heap;
for (auto s : stones)
heap.push(s);
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;
}
};2、 703. 数据流中的第 K 大元素
思路：TopK问题使用小根堆堆解决，priority_queue（默认大根堆）的第三个参数为greater<类型>即为小根堆。
class KthLargest {
public:
int _k;
priority_queue<int, vector<int>, greater<int>> heap;
KthLargest(int k, vector<int>& nums) {
_k = k;
for (auto n : nums) {
heap.push(n);
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);
*/为什么小根堆可以解决TopK问题？
对于设计一个找到数据流中第k大元素的类的问题，我们应该使用小根堆（Min Heap）来实现。下面解释为什么使用小根堆以及如何使用它：
-
为什么使用小根堆:
- 小根堆能够保证堆顶元素是堆中最小的元素。在维护数据流中的第k大元素时，我们希望能够快速访问到第k大的元素，而不是最小的元素。通过维护一个大小为k的小根堆，堆中的元素就是数据流中最大的k个元素，而堆顶元素（最小元素）就是这k个元素中第k大的元素。
- 当新的元素加入时，如果它大于堆顶元素，我们就将它加入堆中，并移除堆顶元素，这样堆的大小仍然保持为k。这样做可以确保堆中始终是数据流中最大的k个元素，而堆顶元素就是这些元素中最小的，即第k大的元素。
-
如何使用小根堆:
- 初始化时，将数组
nums中的元素加入小根堆中，如果元素数量超过k，则移除堆顶元素，以保证堆的大小为k。 - 对于
add方法，每次加入一个新元素时，先将其加入到小根堆中。如果加入后堆的大小超过k，则移除堆顶元素。然后返回堆顶元素，即为当前数据流中第k大的元素。
- 初始化时，将数组
通过使用小根堆，我们可以高效地解决数据流中的第k大元素问题，同时保证时间复杂度和空间复杂度都在合理的范围内。
3、 692. 前K个高频单词
思路：
- 频次统计：首先，使用哈希表记录每个单词出现的频次。
- 优先队列排序：利用优先队列（或小根堆）根据单词的频次和字典序排序，从而找出频次最高的前
k个单词。实现步骤
处理单词列表：
- 利用哈希表统计每个单词出现的次数，确保单词不会重复计数且记录了它们的频次。
使用小根堆选择前 k 大元素：
- 根据问题要求，设计比较器（cmp）：
- 频次不同：频次较少的优先（小根堆性质）。
- 频次相同：字典序较小的优先（大根堆性质）。
- 使用优先队列（小根堆）存储单词及其频次，保证堆的大小不超过
k。- 将每个单词和它的频次插入到堆中，如果堆的大小超过了
k，就移除堆顶元素。获取结果：
- 最终，堆中剩余的就是频次最高的前
k个单词。反向遍历堆，将元素按正确的顺序存入结果列表中。
class Solution {
public:
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;
}
};
vector<string> topKFrequent(vector<string>& words, int k) {
unordered_map<string,int> hash;
for(auto& s:words)
hash[s]++;
priority_queue<PSI,vector<PSI>,cmp> heap;
for(auto& psi:hash){
heap.push(psi);
if(heap.size()>k)
heap.pop();
}
vector<string> ret(k);
for(int i=k-1;i>=0;i--){
ret[i]=heap.top().first;
heap.pop();
}
return ret;
}
};4、 295. 数据流的中位数
实现一个动态中位数查找器
动态数据流中位数查找是一种常见问题，可以通过聪明地运用数据结构来解决。以下是如何通过维护两个堆—一个大根堆和一个小根堆—来实现一个动态中位数查找器的步骤。
解决方法：利用两个堆
算法思路
本解法是一个关于堆数据结构的经典应用。通过将数据流平分或近似平分为两个部分：一个较小部分和一个较大部分—可以高效解决问题：
较小的部分在大根堆（
left）中。较大的部分在小根堆（
right）中。如此设置允许我们在常数时间内获得中位数。
动态添加数据
当有新数据加入时，进行以下步骤以保持两个堆的平衡：
两个堆的大小相同 (
left.size() == right.size()):
若堆为空，直接将
x放入left中。若
x <= left.top()，将x放入left。否则，先将
x放入right，再将right的堆顶元素移到left中。两个堆的大小不相同 (
left.size() > right.size()):
若
x大于或等于right.top()，直接放入right。否则，先将
x放入left，再将left的堆顶元素移到right中。查找中位数
若两个堆的大小相同，中位数是两个堆顶元素的平均值。
- 否则，中位数是
left堆的顶元素。
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;
else return left.top();
}
};
