LeetCode 480. 滑动窗口中位数

滑动窗口月的Hard题,目前有两种解决的主流方案:

1.使用两个堆,一个大顶一个小顶,来计算平均值,C++使用的是priority_queue,即两个优先队列;

2.使用可自己调节的平衡二叉树,把时间和复杂度控制一定范围内,C++给出的是multiset;

 

针对于维护两个堆的思想:

建立两个堆,分别维护两个有序序列:递减序列small,递增序列big;

这样计算mid中位数,只需要关心两者的top堆顶即可;

 

窗口移动的插入新元素,排出旧元素,则需要一定的设计;

总体来说,排出旧元素并不是通过真的排出的,而是先不排出,给予记录后,通过pop堆顶元素排出;

 

针对于这种方法,可能会有疑问:未排出的元素是否会对中位数值造成影响;

 

该方法通过记录一个balance标记来解决这种问题,并且后面如果因为排出元素排空,也会在新的循环中进行重新调整补齐;

详细讲解链接

 

priority_queue<int>small;
priority_queue<int, vector<int>, greater<int>>big;
unordered_map<int, int>mp;

double getmid(int& k) {
    if (k % 2 != 0) {
        return small.top();
    }
    else {
        return (long long)(small.top() + big.top()) * 0.5;
    }
}

vector<double> medianSlidingWindow(vector<int>& nums, int k) {
    vector<double>res;
    for (int i = 0; i < k; i++) {
        small.push(nums[i]);
    }
    for (int i = 0; i < k / 2; i++) {
        big.push(small.top());
        small.pop();
    }
    res.push_back(getmid(k));
    for (int i = k; i < nums.size(); i++) {
        int balance = 0;
        int left = nums[i - k];
        mp[left]++;
        if (!small.empty() && left <= small.top()) {
            balance--;
        }
        else {
            balance++;
        }
        if (!small.empty() && nums[i] <= small.top()) {
            small.push(nums[i]);
            balance++;
        }
        else {
            big.push(nums[i]);
            balance--;
        }
        if (balance > 0) {
            big.push(small.top());
            small.pop();
        }
        if (balance < 0) {
            small.push(big.top());
            big.pop();
        }
        while (!small.empty() && mp[small.top()] > 0) {
            mp[small.top()]--;
            small.pop();
        }
        while (!big.empty() && mp[big.top()] > 0) {
            mp[big.top()]--;
            big.pop();
        }
        res.push_back(getmid(k));
    }
    return res;
}

 

 

 

针对于平衡二叉树:

使用multiset,本质上是构建了一个红黑树;

通过该数据结构将时间复杂度控制在可以接受范围内,但是空间复杂度偏高;

 

每次push和pop后,直接找mid位置即可,很简单;

class Solution {
public:
    vector<double> medianSlidingWindow(vector<int>& nums, int k) {
        vector<double> res;
        multiset<double> st;
        for (int i = 0; i < nums.size(); ++i) {
            if (st.size() >= k) st.erase(st.find(nums[i - k]));
            st.insert(nums[i]);
            if (i >= k - 1) {
                auto mid = st.begin();
                std::advance(mid, k / 2);
                res.push_back((*mid + *prev(mid, (1 - k % 2))) / 2);
            }
        }
        return res;
    }
};

 

上一篇:leetcode.480. 滑动窗口中位数(sliding-window-median)


下一篇:Jquery 图片悬浮放大