C++ में स्लाइडिंग विंडो मेडियन

मान लीजिए कि हमारे पास संख्याओं की एक सूची है, और हमारे पास एक विंडो आकार k है, हमें स्लाइडिंग विंडो तरीके का उपयोग करके माध्यिकाओं की सूची ढूंढनी होगी। तो, अगर वितरण नीचे जैसा है -

यहां हमने माना है कि k 3 है, और परिणाम [1,-1,-1,3,5,6]

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• एक सेट गिरफ्तारी परिभाषित करें
• फ़ंक्शन इंसर्ट को परिभाषित करें (), इसमें x लगेगा,
• गिरफ्तारी में x डालें
• एक फ़ंक्शन को परिभाषित करें हटाएं_(), इसमें x लगेगा,
• यदि यह मौजूद है, तो गिरफ्तारी से x हटाएं
• एक फ़ंक्शन परिभाषित करें getMedian()
• n :=गिरफ्तारी का आकार
• a :=n/2 पर जाएं - गिरफ्तारी के पहले तत्व से 1 कदम आगे, और मान प्राप्त करें
• b :=गिरफ्तारी के पहले तत्व से n/2 कदम आगे बढ़ें, और मान प्राप्त करें
• यदि गिरफ्तारी का आकार है, तो −
  • वापसी ख
• वापसी (ए + बी) * 0.5
• मुख्य विधि से निम्न कार्य करें
• एक सरणी को परिभाषित करें उत्तर
• सरणी एरर साफ़ करें
• इनिशियलाइज़ i :=0 के लिए, जब i करें
• फ़ंक्शन इन्सर्ट को कॉल करें(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, ]