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

中央値（Median）とは

数学における中央値とは、ソート済み（昇順に並べ替えた）数値リストの中間に位置する値のことです。

リストの要素数が偶数の場合、中間の値は1つに定まりません。その場合、中央値は中間にある2つの値の平均（相加平均）として定義されます。

問題の概要

ここでは、JavaScriptの関数を作成します。この関数は、整数の配列 arr を第1引数、ウィンドウサイズを表す数値 num（num ≤ arr.length）を第2引数として受け取ります。

配列 arr 内のサイズ num の各ウィンドウ（連続する部分配列）について中央値を計算し、その結果を新しい配列に順番に格納していきます。そして、反復処理が完了した時点で中央値の配列を返します。

たとえば、関数への入力が次のようだったとします。

const arr = [5, 3, 7, 5, 3, 1, 8, 9, 2, 4, 6, 8];
const num = 3;

この場合、出力は次のようになります。

const output = [5, 5, 5, 3, 3, 8, 8, 4, 4, 6];

出力の解説

各ステップでのウィンドウの状態と中央値は以下の通りです。

実装例

この問題を解くコードは以下の通りです。

const arr = [5, 3, 7, 5, 3, 1, 8, 9, 2, 4, 6, 8];
const num = 3;
const binarySearch = (arr, target, l, r) => {
    while (l < r) {
        const mid = Math.floor((l + r) / 2);
        if (arr[mid] < target) l = mid + 1;
        else if (arr[mid] > target) r = mid;
        else return mid;
    };
    if (l === r) return arr[l] >= target ? l : l + 1;
}
const medianSlidingWindow = (arr = [], num = 1) => {
    let l = 0, r = num - 1, res = [];
    const window = arr.slice(l, num);
    window.sort((a, b) => a - b);
    while (r < arr.length) {
        const median = num % 2 === 0 ? (window[Math.floor(num / 2) - 1] + window[Math.floor(num / 2)]) / 2 : window[Math.floor(num / 2)];
        res.push(median);
        let char = arr[l++];
        let index = binarySearch(window, char, 0, window.length - 1);
        window.splice(index, 1);
        char = arr[++r];
        index = binarySearch(window, char, 0, window.length - 1);
        window.splice(index, 0, char);
    }
    return res;
};
console.log(medianSlidingWindow(arr, num));

コードの解説

このソリューションの基本的なアイデアは、スライディングウィンドウを右へ移動させる際に、二分探索（バイナリサーチ）を使って、右側から入ってくる新しい要素を挿入し、左側から外れる要素を削除するというものです。

毎回ウィンドウ全体を再ソートする代わりに、ソート済みの状態を維持したまま要素の追加・削除を行うことで、計算量を抑えられます。二分探索による挿入位置の特定は O(log n)、splice による挿入・削除は O(n) となるため、全体的には単純な再ソート方式（O(n log n) × ウィンドウ数）よりも効率的な処理が可能です。

また、中央値の計算では num の偶奇を判定しています。偶数の場合は中間の2要素の平均を、奇数の場合は中間の1要素をそのまま中央値として採用します。

実行結果

コンソールへの出力は次のようになります。

[5, 5, 5, 3, 3, 8, 8, 4, 4, 6 ]