หา Median ของ Sliding Window ทุกตำแหน่งใน JavaScript

Median

ค่ากลางของรายการที่เรียงแล้ว หากจำนวนคู่ ให้ค่าเฉลี่ยสองค่ากลาง

ปัญหา

รับอาร์เรย์ arr และขนาดหน้าต่าง num หา median ของทุก sliding window ขนาด num

ตัวอย่าง

const arr = [5, 3, 7, 5, 3, 1, 8, 9, 2, 4, 6, 8]; const num = 3;

ผลลัพธ์: [5, 5, 5, 3, 3, 8, 8, 4, 4, 6]

โค้ดตัวอย่าง (Binary Search + Sorted Window)

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));

คำอธิบาย

ใช้ Binary Search เพื่อ insert/remove ใน sorted window เมื่อเลื่อน sliding window

ผลลัพธ์

[5, 5, 5, 3, 3, 8, 8, 4, 4, 6 ]