C++でスライディングウィンドウの中央値を効率的に求める方法

数列とウィンドウサイズ k が与えられたとき、スライディングウィンドウ方式で各ウィンドウにおける中央値の一覧を求める問題を考えます。例えば、次のような分布の場合をみてみましょう。

ここでは k = 3 としており、得られる結果は [1, -1, -1, 3, 5, 6] となります。

アルゴリズムの考え方

この問題を解くために、以下の手順に従います。

• 順序付き集合（multiset）arr を定義する
• 関数 insert(x) を定義する：x を arr に挿入する
• 関数 delete_(x) を定義する：x が存在すれば arr から削除する
• 関数 getMedian() を定義する
  • n := arr の要素数
  • a := arr の先頭要素から n/2 − 1 ステップ進んだ位置の値
  • b := arr の先頭要素から n/2 ステップ進んだ位置の値
  • arr の要素数が奇数なら b を返す
  • そうでなければ (a + b) × 0.5 を返す

メイン処理の流れ

• 結果格納用の配列 ans を定義する
• arr をクリアする
• i = 0 から k 未満の間、i を1ずつ増やしながら insert(nums[i]) を呼び出し、最初のウィンドウを構築する
• i = k、j = 0 から開始し、i が nums のサイズ未満である間、i と j を1ずつ増やしながら以下を繰り返す
  • getMedian() の戻り値を ans の末尾に追加する
  • delete_(nums[j]) を呼び出して左端の要素を削除する
  • insert(nums[i]) を呼び出して右側に新しい要素を追加する
• 最後に getMedian() の戻り値を ans の末尾に追加する
• ans を返す

それでは、理解を深めるために以下の実装例を見てみましょう。

実装例（C++）

#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));
}

計算量について

C++の multiset は平衡二分探索木で実装されているため、要素の挿入・削除・検索はいずれも O(log k) で行えます。したがって、このアルゴリズム全体の計算量は O(n log k) となります。ウィンドウごとに毎回ソートし直す素朴な手法（O(n・k log k)）と比べて、大幅に効率化できる点が大きなポイントです。

入力

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

出力

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