Sliding Window Median in C++

Suppose we have a list of numbers, and we have one window size k, we have to find the list of medians using sliding window manner. So, if the distribution is like below −

Here we have considered the k is 3, and the result will be [1,-1,-1,3,5,6]

To solve this, we will follow these steps −

• Define one set arr
• Define a function insert(), this will take x,
• insert x into arr
• Define a function delete_(), this will take x,
• delete x from arr, if this exists
• Define a function getMedian()
• n := size of arr
• a := jump to n/2 – 1 step forward of first element of arr, and get the value
• b := jump to n/2 step forward of first element of arr, and get the value
• if size of arr, then −
  • return b
• return (a + b) * 0.5
• From the main method do the following
• Define an array ans
• clear the array arr
• for initialize i := 0, when i < k, update (increase i by 1), do −
  • call the function insert(nums[i])
• for initialize i := k, j := 0, when i < size of nums, update (increase i by 1), (increase j by 1), do −
  • insert returned value of getMedian() at the end of ans
  • call the function delete_(nums[j])
  • call the function insert(nums[i])
• insert returned value of getMedian() at the end of ans
• return ans

Let us see the following implementation to get better understanding −

Example

 Live Demo

#include <bits/stdc++.h> using namespace std; void print_vector(vector<auto> v){    cout << "[";    for(int i = 0; i<v.size(); i++){       cout << v[i] << ", ";    }    cout << "]"<<endl; } class Solution { public:    multiset <double> arr;    void insert(double x){       arr.insert(x);    }    void delete_(double x){       arr.erase(arr.find(x));    }    double getMedian(){       int n = arr.size();       double a = *next(arr.begin(), n / 2 - 1);       double b = *next(arr.begin(), n / 2);       if(arr.size() & 1)return b;       return (a + b) * 0.5;    }    vector<double> medianSlidingWindow(vector<int>& nums, int k) {       vector <double> ans;       arr.clear();       for(int i = 0; i < k; i++){          insert(nums[i]);       }       for(int i = k, j = 0; i < nums.size(); i++, j++){          ans.push_back(getMedian());          delete_(nums[j]);          insert(nums[i]);       }       ans.push_back(getMedian());       return ans;    } }; main(){    Solution ob;    vector<int> v = {1,3,-1,-3,5,3,6,8};    print_vector(ob.medianSlidingWindow(v, 3)); }

Input

{1,3,-1,-3,5,3,6,8}

Output

[1, -1, -1, 3, 5, 6, ]