Home LeetCode-480 Sliding Window Median
Post
Cancel

LeetCode-480 Sliding Window Median

Description

给出数组\(nums[]\),窗口大小\(k\),求滑动窗口中的(排序后)中值。具体见下面样例:

Window position                Median
---------------                -----
[1  3  -1] -3  5  3  6  7        1
 1 [3  -1  -3] 5  3  6  7       -1
 1  3 [-1  -3  5] 3  6  7       -1
 1  3  -1 [-3  5  3] 6  7        3
 1  3  -1  -3 [5  3  6] 7        5
 1  3  -1  -3  5 [3  6  7]       6

Constraints

  • \(nums[]\)长度不超\(10^5\)
  • \(nums[i]\)数值在整型int范围内

Solution

两个对顶堆的事情,麻烦在于corner case。这里可以用不变式来避免多种情况的讨论,设不变式为:

  • \( size(small\ set) \ge size(large\ set) \)
  • \( size(small\ set) \le size(large\ set) + 1 \)

也就是一般2个集合都是等同大小的,最多允许\(small\ set\)多出1个元素

Code

class Solution {
public:
    vector<double> medianSlidingWindow(vector<int>& nums, int k) {
        multiset<int> ss; // small set
        multiset<int> ls; // large set
        vector<double> ans;
        for(int i = 0; i < nums.size(); ++i) {
            ss.insert(nums[i]);
            // 不管怎样,先交换一下
            if(!ls.empty()) {
                auto minLarge = ls.begin();
                auto maxSmall = --ss.end();
                int mn = min(*minLarge, *maxSmall);
                int mx = max(*minLarge, *maxSmall);
                ls.erase(minLarge);
                ss.erase(maxSmall);
                ls.insert(mx);
                ss.insert(mn);
            }
            // 如果存在违反不变式
            if(ss.size() > ls.size() + 1) {
                auto siter = --ss.end();
                int v = *siter;
                ss.erase(siter);
                ls.insert(v);
            }
            if(i >= k-1) {
                if(ss.size() > ls.size()) ans.push_back(*--ss.end());
                else ans.push_back( (0.0 + *--ss.end() + *ls.begin()) / 2.0 );
                int v = nums[i - (k-1)];
                auto siter = ss.find(v);
                // 考虑到下一次还是从ss里插入的,这样不会违反不变式
                if(siter != ss.end()) {
                    ss.erase(siter);
                // 如果实在没办法,那就需要往ss里挪用一个
                // 下一次插入ss后仍然满足不变式
                } else {
                    auto liter = ls.find(v);
                    ls.erase(liter);
                    ls.insert(*--ss.end());
                    ss.erase(--ss.end());
                }
            }
        }
        return ans;
    }
};

LeetCode-480 Sliding Window Median

This post is licensed under CC BY 4.0 by the author.
Contents