Tìm giá trị trung bình cho mọi cửa sổ trong JavaScript

Trung vị

Trung vị trong toán học, trung vị là giá trị giữa trong danh sách số nguyên có thứ tự (đã sắp xếp).

Nếu kích thước của danh sách là chẵn và không có giá trị ở giữa. Median là giá trị trung bình (trung bình) của hai giá trị giữa.

Vấn đề

Chúng tôi được yêu cầu viết một hàm JavaScript nhận một mảng Số nguyên, arr, làm đối số đầu tiên và một số num (num <=length of array arr) làm đối số thứ hai.

Bây giờ đối với mỗi cửa sổ có kích thước num trong mảng arr, hàm của chúng ta sẽ tính giá trị trung bình và đẩy giá trị trung bình đó vào một mảng mới và cuối cùng khi kết thúc lặp lại trả về mảng trung bình đó.

Ví dụ:nếu đầu vào của hàm là -

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

Sau đó, kết quả đầu ra phải là -

const output = [5, 5, 5, 3, 3, 8, 8, 4, 4, 6];

Giải thích đầu ra:

Chỉ mục bắt đầu	Cửa sổ hiện tại	Cửa sổ được sắp xếp hiện tại	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ã cho điều này sẽ là -

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 mã:

Ý tưởng đằng sau giải pháp này là sử dụng tìm kiếm nhị phân để chèn số bên phải và loại bỏ số bên trái khi di chuyển cửa sổ trượt sang bên phải.

Đầu ra

Và đầu ra trong bảng điều khiển sẽ là -

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