การหาค่ามัธยฐานสำหรับทุกหน้าต่างใน JavaScript

ค่ามัธยฐาน

ค่ามัธยฐานในวิชาคณิตศาสตร์ ค่ามัธยฐานคือค่ากลางในรายการจำนวนเต็มเรียงลำดับ (เรียงแล้ว)

หากขนาดของรายการเท่ากัน และไม่มีค่ากลาง ค่ามัธยฐานคือค่าเฉลี่ย (ค่าเฉลี่ย) ของค่ากลางทั้งสองค่า

ปัญหา

เราจำเป็นต้องเขียนฟังก์ชัน JavaScript ที่รับอาร์เรย์ของ Integers, arr เป็นอาร์กิวเมนต์แรกและตัวเลข num (num <=length of array arr) เป็นอาร์กิวเมนต์ที่สอง

ตอนนี้ สำหรับแต่ละหน้าต่างของ size num ในอาร์เรย์ arr ฟังก์ชันของเราควรคำนวณค่ามัธยฐานและผลักค่ามัธยฐานนั้นไปยังอาร์เรย์ใหม่และสุดท้ายเมื่อสิ้นสุดการวนซ้ำจะคืนค่าอาร์เรย์มัธยฐานนั้น

ตัวอย่างเช่น หากอินพุตของฟังก์ชันคือ −

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

คำอธิบายผลลัพธ์:

ตัวอย่าง

รหัสสำหรับสิ่งนี้จะเป็น −

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 ]