मान लीजिए हमारे पास संख्याओं की एक सूची है, और हमारे पास एक विंडो आकार k है, हमें स्लाइडिंग विंडो तरीके से मेडियन की सूची ढूंढनी है। तो, यदि वितरण नीचे जैसा है -
| विंडो स्थिति | मेडियन | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| 1 | 3 | -1 | -3 | 5 | 3 | 6 | 8 | 1 | |
| 1 | 3 | -1 | -3 | 5 | 3 | 6 | 8 | -1 | |
| 1 | 3 | -1 | -3 | 5 | 3 | 6 | 8 | -1 | |
| 1 | 3 | -1 | -3 | 5 | 3 | 6 | 8 | 3 | |
| 1 | 3 | -1 | -3 | 5 | 3 | 6 | 8 | 5 | |
| 1 | 3 | -1 | -3 | 5 | 3 | 6 | 8 | 6 | |
यहां हमने k को 3 माना है, और परिणाम [1,-1,-1,3,5,6] होगा।
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे -
- एक सेट arr परिभाषित करें
- एक फ़ंक्शन insert() परिभाषित करें, जो x लेगा,
- x को arr में डालें
- एक फ़ंक्शन delete_() परिभाषित करें, जो x लेगा,
- यदि x मौजूद है तो इसे arr से हटाएं
- एक फ़ंक्शन getMedian() परिभाषित करें
- n := arr का आकार
- a := arr के पहले तत्व से n/2 - 1 चरण आगे जाएं और मान प्राप्त करें
- b := arr के पहले तत्व से n/2 चरण आगे जाएं और मान प्राप्त करें
- यदि arr का आकार विषम है, तो -
- b लौटाएं
- (a + b) * 0.5 लौटाएं
- मुख्य विधि से निम्नलिखित करें
- एक सरणी ans परिभाषित करें
- सरणी arr को साफ़ करें
- i := 0 से आरंभ करें, जब i < k, अपडेट करें (i को 1 से बढ़ाएं), करें -
- फ़ंक्शन insert(nums[i]) को कॉल करें
- i := k, j := 0 से आरंभ करें, जब i < nums का आकार, अपडेट करें (i को 1 से बढ़ाएं), (j को 1 से बढ़ाएं), करें -
- getMedian() के लौटाए गए मान को ans के अंत में डालें
- फ़ंक्शन delete_(nums[j]) को कॉल करें
- फ़ंक्शन insert(nums[i]) को कॉल करें
- getMedian() के लौटाए गए मान को ans के अंत में डालें
- ans लौटाएं
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#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, ]
