今日学习记录
1. 480. 滑动窗口中位数
关键词：对顶堆 滑动窗口 哈希表
问题分析：
给定一个长度的滑窗,找到每次滑窗中位数
核心思路: 滑窗不用多说,这个题的数据特别弱,可以使用 multiset 有序集合直接进行插入和删除,直接找到中位数 但是这样就没意思了,标准解法就是对顶堆
对顶堆
找中位数用对顶堆是常规操作了,但是此题最让人难受的就是这个滑窗的入和出的操作,直接到堆中修改是不现实的,所以我们使用哈希表来进行记录删除的元素
我们只用标记要删除的数据就行,已经删除的元素在堆中其实是不影响的,只有当被删除的元素在堆顶的时候才会造成影响,其他的则不影响堆的顺序,但是删除的元素并没有删除,不能直接读取堆的长度,要单独记录左右堆的长度(代表存在的元素数量),这个想法是差不多的
当时我没有意识到在两个堆之间转移元素时,你不知道被删的元素移到哪里了,会导致左右存在元素数量混乱
实现细节
我们要清楚我们要干什么,两个优先队列,要记录每个堆的存在元素数量,要进行堆的平衡分配,对于每个优先队列,其中的删除数据(可以知道删除数据的具体在哪个堆)都是独立的,我们可以先写着试试,发现有很多操作是相同的,而且我们要频繁的判断堆顶是否为删除元素,这里实现时确实很难写,但是我们可以把这些功能整合封装起来,自己写一个堆,接下来我来详细描述这个结构体 成员变量:
- 优先队列(大小根堆)
- 哈希表(记录删除元素数量),因为有可能重复
- 实际大小
- 删除判断,用来删除堆顶的元素,下面要频繁使用 方法:
- size
- delet,并将实际大小减一
- top,再返回堆顶
- push,并将实际大小加一
- pop,所以要先进行删除判断,再进行 pop 并返回 top
- push_pop pop(就是先 push 后 pop)
**最终代码：
template<typename T, typename Compare = less<T>>
class lazyheap{
priority_queue<T,vector<T>,Compare> pq;
unordered_map<T,int> mp;
int sz = 0;
void remove(){
while(!pq.empty()&&mp[pq.top()]>0){
mp[pq.top()]--;
pq.pop();
}
}
public:
int size(){
return sz;
}
void delet(T x){
mp[x]++;
sz--;
}
T top(){
remove();
return pq.top();
}
T pop(){
remove();
T x = pq.top();
pq.pop();
sz--;
return x;
}
void push(T x){
pq.push(x);
sz++;
}
T push_pop(T x){
if(sz>0&&Compare()(x,top())){
pq.push(x);
x = pq.top();
pq.pop();
}
return x;
}
};
class Solution {
public:
vector<double> medianSlidingWindow(vector<int>& nums, int k) {
int n = nums.size();
vector<double> ans(n - k + 1);
lazyheap<int> left; // 最大堆
lazyheap<int, greater<int>> right; // 最小堆
for (int i = 0; i < n; i++) {
int in = nums[i];
if (left.size() == right.size()) left.push(right.push_pop(in));
else right.push(left.push_pop(in));
int l = i + 1 - k;
if (l<0) continue;
if(k%2) ans[l] = left.top();
else ans[l] = ((long long) left.top() + right.top()) / 2.0;
int out = nums[l];
if(out <= left.top()){
left.delet(out);
if (left.size() < right.size()) left.push(right.pop());
} else{
right.delet(out);
if (left.size() > right.size() + 1) right.push(left.pop());
}
}
return ans;
}
};学到的点：
- 自写对顶堆