C++ এ স্লাইডিং উইন্ডো মিডিয়ান

ধরুন আমাদের সংখ্যার একটি তালিকা আছে, এবং আমাদের একটি উইন্ডো সাইজ k, আমাদের স্লাইডিং উইন্ডো পদ্ধতি ব্যবহার করে মধ্যমাগুলির তালিকা খুঁজে বের করতে হবে। সুতরাং, যদি বন্টন নিচের মত হয় -

এখানে আমরা বিবেচনা করেছি k হল 3, এবং ফলাফল হবে [1,-1,-1,3,5,6]

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• এক সেট arr সংজ্ঞায়িত করুন
• একটি ফাংশন সন্নিবেশ () সংজ্ঞায়িত করুন, এটি x লাগবে,
• এআর-এ x ঢোকান
• একটি ফাংশন সংজ্ঞায়িত করুন delete_(), এটি x লাগবে,
• আর থেকে x মুছুন, যদি এটি বিদ্যমান থাকে
• একটি ফাংশন getMedian()
সংজ্ঞায়িত করুন
• n :=arr এর আকার
• a :=n/2-এ ঝাঁপ দাও - arr-এর প্রথম উপাদান থেকে 1 ধাপ এগিয়ে, এবং মান পান
• b :=arr-এর প্রথম উপাদান থেকে n/2 ধাপ এগিয়ে যান এবং মান পান
• যদি arr এর আকার হয়, তাহলে −
  • ফেরত b
• রিটার্ন (a + b) * 0.5
• প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন
• একটি অ্যারে উত্তর সংজ্ঞায়িত করুন
• অ্যারে সাফ করুন
• আরম্ভ করার জন্য i :=0, যখন i করুন
• ফাংশন সন্নিবেশ কল করুন(সংখ্যা[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, ]