数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会研究
服装研究
法学研究在JavaScript中查找每个窗口的中位数
中位数
在数学中，中位数是有序（排序）整数列表中的中间值。
如果列表的大小是偶数，并且没有中间值，则中位数是两个中间值的平均值。
问题
我们需要编写一个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];
输出解释
| 起始索引 | 当前窗口 | 当前排序窗口 | 中位数 |
|---|---|---|---|
| 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 ]
更新于：2021年3月4日
735 次浏览
广告