7-line C++ O(N*logk) solution using multiset for sliding window (comments and detailed explanation)


  • 0

    This is my minor changed version of @StefanPochmann 's multiset solution. Originally, I was using two iterators L, R for middle left and middle right positions of sliding window (L==R if k is odd), but using two iterators seems to be redundant.

    Note:

    • Iterator m is always pointing to the middle right position of sliding window, i.e., m is the k/2th value (zero-based).
    • When the sliding window moves towards right for one position, m moves at most twice to re-position to the updated middle right position.
    • Median value med of a sliding window is given by med = *m/2. + *ml/2. to handle possible overflow, where ml points to middle left postion, i.e., (k-1)/2th value in sliding window.
        vector<double> medianSlidingWindow(vector<int>& nums, int k) 
        {
            multiset<int> w(nums.begin(), nums.begin()+k);   // first sliding window
            auto m = next(w.begin(), k/2);                   // middle (right) position
            vector<double> med = {*m/2.+*next(m,k%2-1)/2.};  // median array
            for (auto i = nums.begin(); i < nums.end()-k; w.erase(w.lower_bound(*i++)), med.push_back(*m/2.+*next(m,k%2-1)/2.)) 
            {
                if (w.insert(*(i+k)), *(i+k) < *m) --m; // move to middle (left)
                if (*i <= *m) ++m; // back to middle (right)
            }
            return med;
        }
    

Log in to reply
 

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