JavaScript에서 모든 창의 중앙값 찾기

중앙값

수학에서 중앙값은 정렬된(정렬된) 정수 목록의 중간 값입니다.

목록의 크기가 짝수이고 중간 값이 없는 경우. 중앙값은 두 중간 값의 평균(평균)입니다.

문제

정수 배열 arr을 첫 번째 인수로, 숫자 num(num <=배열 arr의 길이)을 두 번째 인수로 사용하는 JavaScript 함수를 작성해야 합니다.

이제 배열 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];

출력 설명:

예시

이에 대한 코드는 -

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 ]