C++でのスライディングウィンドウの中央値

数値のリストがあり、1つのウィンドウサイズがkであるとすると、スライディングウィンドウ方式を使用して中央値のリストを見つける必要があります。したがって、分布が以下のような場合-

ここでは、kが3であると見なし、結果は[1、-1、-1,3,5,6]

これを解決するには、次の手順に従います-

• 1セットの到着を定義する
• 関数insert（）を定義します。これにはxが必要です。
• xをarrに挿入
• 関数delete_（）を定義します。これにはxが必要です。
• 存在する場合は、arrからxを削除します
• 関数getMedian（）を定義します
• n：=arrのサイズ
• a：=n / 2にジャンプ– arrの最初の要素の1ステップ先に進み、値を取得します
• b：=arrの最初の要素のn/ 2ステップ先にジャンプし、値を取得します
• arrのサイズの場合、-
  • return b
• return（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, ]