C++ two multiset solution


  • 1
    H

    Similar idea as 295. Find Median from Data Stream
    Keep a max heap and a min heap
    But in this case, we need to keep on removing elements out of the window
    So use multiset insead of heap
    T = O(n*log(k)), S = O(k)

    class Solution {
    public:
        vector<double> medianSlidingWindow(vector<int>& nums, int k) {
            vector<double> res;
            multiset<int> u, l;
            int n = nums.size();
            for (int i = 0; i < n; ++i) {
                
                // Insert new number
                if (u.empty() or nums[i] >= *u.begin())
                    u.insert(nums[i]);
                else l.insert(nums[i]);
                
                // Remove number out of the window
                if (i >= k) {
                    if (nums[i-k] >= *u.begin())
                        u.erase(u.find(nums[i-k]));
                    else l.erase(l.find(nums[i-k]));
                }
                
                // Balance the size of two sets
                while (u.size() < l.size()) {
                    u.insert(*l.rbegin());
                    l.erase(--l.end());
                }
                while (u.size() > l.size() + 1) {
                    l.insert(*u.begin());
                    u.erase(u.begin());
                }
                
                // Push back median
                if (i >= k-1) {
                    if (k & 1) res.push_back(*u.begin());
                    else res.push_back(((double)*u.begin() + *l.rbegin()) / 2);
                }
            }
            return res;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.