資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告