JavaScriptですべてのウィンドウの中央値を見つける

中央値

数学の中央値。中央値は、順序付けられた（ソートされた）整数リストの中央値です。

リストのサイズが偶数で、中間値がない場合。中央値は、2つの中間値の平均（平均）です。

問題

最初の引数として整数の配列arrを取り、2番目の引数として数値num（num <=配列arrの長さ）を受け取るJavaScript関数を作成する必要があります。

これで、配列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));

コードの説明：

このソリューションの背後にある考え方は、スライディングウィンドウを右に移動するときに、バイナリ検索を使用して右の数字を挿入し、左の数字を削除することです。

出力

そして、コンソールの出力は-

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