O(nlogk) C++ Multiset with Mid-Iterator Further Thought


  • 0

    StefanPochmann's solution is great. His solution maintains the mid-iterator by the smaller half. Thus I want to try to maintain the mid-iterator with the larger half. And this turned out to be non-trival and I gained a lot from thinking about it, so I post my mirroring solution here along with my respect. The key points are:

    1. maintain the invariant: guarantee the mid-iterator movement happens on the correct situation.
      For smaller half solution it means mid-- when inserting nums[i] < *mid and mid++ when removingnums[i-k] <= *mid; for larger half solution it means mid++ when inserting nums[i] >= *mid and mid-- when removing nums[i-k] >= *mid, thanks to point 2.
    2. The C++ 11 standard: newly inserted elements follow their equivalents already in the container. *This makes operating on the smaller half easier.
    3. lower_bound and upper_bound semantic
    class Solution {
    public:
        vector<double> medianSlidingWindow(vector<int>& nums, int k) {
            multiset<int> window(nums.begin(), nums.begin() + k);
            auto mid = next(window.begin(), k / 2);
            vector<double> medians;
            for (int i=k; ; i++) {
                // Push the current median.
                medians.push_back((double(*mid) + *prev(mid, 1 - k%2)) / 2);
        
                // If all done, return.
                if (i == nums.size())
                    return medians;
                    
                // Insert nums[i].
                window.insert(nums[i]);
                if (nums[i] >= *mid)
                    mid++;
        
                // Erase nums[i-k].
                if (nums[i-k] >= *mid)
                    mid--;
                window.erase(prev(window.upper_bound(nums[i-k]),1));
            }
        }
    };
    

Log in to reply
 

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