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

স্লাইডিং উইন্ডো মেডিয়ান সমস্যা

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

এখানে ফলাফল হবে: [1, -1, -1, 3, 5, 6]

সমাধানের পদ্ধতি

এই সমস্যাটি সমাধানের জন্য আমরা একটি মাল্টিসেট (multiset) ব্যবহার করব, যা স্বয়ংক্রিয়ভাবে উপাদানগুলো সাজিয়ে রাখে। নিচে ধাপগুলো দেওয়া হলো:

• একটি মাল্টিসেট arr সংজ্ঞায়িত করুন
• insert() ফাংশন তৈরি করুন যা একটি মান x সেটে যোগ করবে
• delete_() ফাংশন তৈরি করুন যা একটি মান x সেট থেকে মুছে ফেলবে (যদি থাকে)
• getMedian() ফাংশন তৈরি করুন:
  • n := arr.size()
  • a := arr.begin() + n/2 - 1 vị置的 মান
  • b := arr.begin() + n/2 vị置的 মান
  • যদি n বিজোড় হয়, b ফেরত দিন
  • অন্যথায় (a + b) * 0.5 ফেরত দিন
• মূল ফাংশন থেকে:
  • একটি উত্তর অ্যারে ans এবং খালি arr ঘোষণা করুন
  • প্রথম k টি উপাদান arr-এ যোগ করুন
  • i = k থেকে nums.size()-1 পর্যন্ত লুপ চালান:
    • বর্তমান মেডিয়ান ans-এ যোগ করুন
    • পুরানো উপাদান nums[j] মুছুন
    • নতুন উপাদান nums[i] যোগ করুন
  • শেষ মেডিয়ান ans-এ যোগ করুন
  • ans ফেরত দিন

C++ কোড উদাহরণ

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<double> 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;
    }
};

int main() {
    Solution ob;
    vector<int> v = {1, 3, -1, -3, 5, 3, 6, 8};
    print_vector(ob.medianSlidingWindow(v, 3));
    return 0;
}

ইনপুট

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

আউটপুট

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