Trung vị (Median)
Trung vị là giá trị giữa trong danh sách số nguyên đã sắp xếp. Nếu số lượng chẵn, trung vị là trung bình cộng hai giá trị giữa.
Vấn đề
Cần viết hàm JS nhận mảng arr và số num (num ≤ độ dài mảng). Với mỗi cửa sổ kích thước num, tính trung vị, đưa vào mảng kết quả.
Ví dụ:
const arr = [5, 3, 7, 5, 3, 1, 8, 9, 2, 4, 6, 8]; const num = 3;
Kết quả:
const output = [5, 5, 5, 3, 3, 8, 8, 4, 4, 6];
Giải thích:
| Chỉ số bắt đầu | Cửa sổ hiện tại | Cửa sổ đã sắp xếp | Trung vị |
|---|---|---|---|
| 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 |
Ví dụ
Mã thực hiện:
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));
Giải thích code:
Ý tưởng: dùng tìm kiếm nhị phân để chèn/xóa phần tử khi cửa sổ trượt sang phải.
Kết quả
Kết quả in ra console:
[5, 5, 5, 3, 3, 8, 8, 4, 4, 6 ]