查找JavaScript中每个窗口的中位数

中位数

在数学中，中位数是ordered(sorted)整数列表中的中间值。

如果列表的大小是偶数，并且没有中间值。中位数是两个中间值的平均值（平均值）。

问题

我们需要编写一个JavaScript函数，该函数将Integers数组arr作为第一个参数，并将数字num（num <=数组arr的长度）作为第二个参数。

现在，对于数组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 ]