在 JavaScript 中为每个窗口寻找中位数
javascriptweb developmentfront end technology
中位数
数学中的中位数，中位数是有序(排序)整数列表中的中间值。
如果列表的大小是偶数，并且没有中间值。中位数是两个中间值的平均值。
问题
我们需要编写一个 JavaScript 函数，该函数将一个整数数组 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];
输出说明:
| Starting Index | Current Window | Current Sorted window | Median |
|---|---|---|---|
| 0 | [5, 3, 7] | [3, 5, 7] | 5 |
| 1 | [3, 7, 5] | [3, 5, 7] | 5 |
| 2 | [7, 5, 3] | [3, 5, 7] | 5 |
| 3 | [5, 3, 1] | [1, 3, 5] | 3 |
| 4 | [3, 1, 8] | [1, 3, 8] | 3 |
| 5 | [1, 8, 9] | [1, 8, 9] | 8 |
| 6 | [8, 9, 2] | [2, 8, 9] | 8 |
| 7 | [9, 2, 4] | [2, 4, 9] | 4 |
| 8 | [2, 4, 6] | [2, 4, 6] | 4 |
| 9 | [4, 6, 8] | [4, 6, 8] | 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 ]
