题解 | #滑动窗口中位数#

思路一开始就有了,本以为会很快通过,结果被边界条件卡了很久.

显然要用到滑动窗口,窗口每次滑动时会加入和删除一个数字.

容易想到使用std::multiset来维护递增序列,并且std::multiset的插入和删除都是O(logK).

那么如何找到这个序列的中位数呢?

- 初始化时,需要从multiset的首元素开始向后迭代到窗口的中央.

- 窗口滑动时需要根据删除和添加的元素与中位数迭代器的相对位置对其进行向前或者向后,最多一位的调整.

大概思路就是这样,但是实现的时候需要注意: k的奇偶性,窗口滑动时如何调整中位数迭代器

当然也可以自己实现平衡树,记录每一棵子树的节点数量来查找中位数.

复杂度: O(NlogK)

#include <set>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @param k int整型 
     * @return double浮点型vector
     */
    vector<double> slidewindow(vector<int>& nums, int k) {
        vector<double> ret;
        for(int i=0;i<k;++i)mset.insert(nums[i]);
        auto mid=mset.begin();
        for(int i=0;i<(k+1)/2-1;++i)mid++;
        int l=0,r=k;
        while(true){
            if(k%2==1) ret.push_back(*mid);
            else{
                auto a=mid;
                ++a;
                ret.push_back((*mid+*a)/2.);
            }
            if(r==nums.size())break;
            mset.insert(nums[r]);
            if(nums[r]<*mid)--mid;
            auto to_erase=mset.lower_bound(nums[l]);
            if(nums[l]<=*mid){
                ++mid;
            }
            mset.erase(to_erase);
            l++,r++;
        }
        return ret;
    }
    multiset<int> mset;
};