मान लीजिए हमारे पास एक सॉर्टेड इंटीजर ऐरे nums है, एलिमेंट्स की रेंज समावेशी रेंज [lower, upper] में है, हमें मिसिंग रेंजेस ढूंढनी हैं।
इसलिए, यदि इनपुट है nums = [0, 1, 3, 50, 75], और lower मान 0 है और upper मान 99 है, तो आउटपुट होगा ["2", "4->49", "51->74", "76->99"]
इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:
एक ऐरे nums परिभाषित करें
एक सेट v परिभाषित करें
i := 0 से शुरू करें, जब i < t का आकार, i बढ़ाते हुए, करें -
यदि t[i] v में नहीं है, तो -
t[i] को v में डालें
t[i] को nums के अंत में डालें
एक ऐरे ret परिभाषित करें
curr := lower
i := 0, n := nums का आकार
जब curr <= upper, करें -
यदि i < n और nums[i] curr के समान है, तो -
(i को 1 से बढ़ाएं)
(curr को 1 से बढ़ाएं)
अन्यथा
temp := curr को स्ट्रिंग में बदलें
(curr को 1 से बढ़ाएं)
यदि i < n और nums[i] curr के समान है, तो -
temp को ret के अंत में डालें
बाकी भाग को अनदेखा करें, अगले इटरेशन पर जाएं
अन्यथा
यदि i, n के समान है, तो -
यदि curr <= upper, तो -
temp := "->"
temp := temp + upper को स्ट्रिंग के रूप में
curr := upper + 1
temp को ret के अंत में डालें
अन्यथा
temp := "->"
curr := nums[i]
temp := temp + (curr - 1) को स्ट्रिंग के रूप में
curr := nums[i]
temp को ret के अंत में डालें
ret लौटाएं
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
#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: vector<string> findMissingRanges(vector<int>& t, int lower, int upper) { vector <int> nums; set <long long int> v; for(int i = 0; i < t.size(); i++){ if(!v.count(t[i])){ v.insert(t[i]); nums.push_back(t[i]); } } vector < string > ret; long long int curr = lower; int i = 0; int n = nums.size(); while(curr <= upper){ if(i < n && nums[i] == curr){ i++; curr++; } else{ string temp = to_string(curr); curr++; if(i < n && nums[i] == curr){ ret.push_back(temp); continue; } else{ if(i == n){ if(curr <= upper){ temp += "->"; temp += to_string(upper); curr = (long long int )upper + 1; } ret.push_back(temp); } else{ temp += "->"; curr = nums[i]; temp += to_string(curr - 1); curr = nums[i]; ret.push_back(temp); } } } } return ret; } }; main(){ Solution ob; vector<int> v = {0,1,3,50,75}; print_vector(ob.findMissingRanges(v, 0, 99)); }इनपुट
{0,1,3,50,75}, 0, 99आउटपुट
[2, 4->49, 51->74, 76->99, ]
