C++의 슬라이딩 윈도우 중앙값

숫자 목록이 있고 하나의 창 크기 k가 있다고 가정하면 슬라이딩 창 방식을 사용하여 중앙값 목록을 찾아야 합니다. 따라서 분포가 아래와 같으면 -

여기서 k는 3이고 결과는 [1,-1,-1,3,5,6]

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 한 세트를 정의하십시오.
• insert() 함수를 정의합니다. x가 필요합니다.
• x를 arr에 삽입
• delete_() 함수를 정의하면 x가 걸립니다.
• arr에서 x 삭제(있는 경우)
• getMedian() 함수 정의
• n :=arr의 크기
• a :=n/2로 점프 – arr의 첫 번째 요소보다 1단계 앞으로 이동하고 값을 가져옵니다.
• b :=arr의 첫 번째 요소의 n/2 단계 앞으로 이동하여 값을 가져옵니다.
• arr의 크기이면 -
  • 반환
• 반환 (a + b) * 0.5
• 기본 방법에서 다음을 수행합니다.
• 배열 정의
• 배열 삭제
• 초기화 i의 경우:=0, i
• insert(nums[i]) 함수 호출

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
public:
   multiset <double> arr;
   void insert(double x){
      arr.insert(x);
   }
   void delete_(double x){
      arr.erase(arr.find(x));
   }
   double getMedian(){
      int n = arr.size();
      double a = *next(arr.begin(), n / 2 - 1);
      double b = *next(arr.begin(), n / 2);
      if(arr.size() & 1)return b;
      return (a + b) * 0.5;
   }
   vector<double> medianSlidingWindow(vector<int>& nums, int k) {
      vector <double> ans;
      arr.clear();
      for(int i = 0; i < k; i++){
         insert(nums[i]);
      }
      for(int i = k, j = 0; i < nums.size(); i++, j++){
         ans.push_back(getMedian());
         delete_(nums[j]);
         insert(nums[i]);
      }
      ans.push_back(getMedian());
      return ans;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,3,-1,-3,5,3,6,8};
   print_vector(ob.medianSlidingWindow(v, 3));
}

입력

{1,3,-1,-3,5,3,6,8}

출력

[1, -1, -1, 3, 5, 6, ]