मान लीजिए हमारे पास पूर्णांकों का एक डेटा स्ट्रीम इनपुट है, ये a1, a2, ..., an, ... जैसे हैं, हमें अब तक देखी गई संख्याओं को असंयुक्त अंतराल की सूची के रूप में सारांशित करना है। उदाहरण के लिए, मान लीजिए इनपुट पूर्णांक 1, 3, 8, 2, 7, ... हैं, तो सारांश होगा -
[1,1]
[1, 1], [3, 3]
[1, 1], [3, 3], [8, 8]
[1, 3], [8, 8]
[1, 3], [7, 8].
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे -
nums नामक एक सेट बनाएं
आरंभकर्ता में, low := -inf और high := inf सेट करें
addNum विधि से जो num को इनपुट के रूप में लेता है, num को सेट nums में डालें
get interval विधि से, निम्नलिखित करें -
एक 2D सरणी ret परिभाषित करें
it := सेट nums का प्रारंभ तत्व
जब it सेट में है, करें -
x := it का मान
यदि ret खाली है या ret के अंतिम तत्व के इंडेक्स 1 पर तत्व + 1 < x, तो,
जोड़ी { x, x } को ret के अंत में डालें
अन्यथा
ret के अंतिम तत्व के इंडेक्स 1 पर मौजूद तत्व को 1 से बढ़ाएं
it को अगले तत्व पर ले जाएं
ret लौटाएं
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -
#include <bits/stdc++.h> using namespace std; void print_vector(vector<vector<auto> > v){ cout << "["; for(int i = 0; i<v.size(); i++){ cout << "["; for(int j = 0; j <v[i].size(); j++){ cout << v[i][j] << ", "; } cout << "],"; } cout << "]"<<endl; } class SummaryRanges { public: set <int> nums; int low, high; SummaryRanges() { low = INT_MAX; high = INT_MIN; } void addNum(int val) { nums.insert(val); } vector<vector<int>> getIntervals() { vector < vector <int> > ret; set <int> :: iterator it = nums.begin(); while(it != nums.end()){ int x = *it; if(ret.empty() || ret.back()[1] + 1 < x){ ret.push_back({x, x}); } else { ret.back()[1]++; } it++; } return ret; } }; main(){ SummaryRanges ob; ob.addNum(1); print_vector(ob.getIntervals()); ob.addNum(3); print_vector(ob.getIntervals()); ob.addNum(8); print_vector(ob.getIntervals()); ob.addNum(2); print_vector(ob.getIntervals()); ob.addNum(7); print_vector(ob.getIntervals()); }इनपुट
कक्षा को आरंभ करें, फिर एक-एक करके तत्व डालें और अंतराल देखें। तो तत्व हैं [1,3,8,2,7]
आउटपुट
[[1, 1, ],] [[1, 1, ],[3, 3, ],] [[1, 1, ],[3, 3, ],[8, 8, ],] [[1, 3, ],[8, 8, ],] [[1, 3, ],[7, 8, ],]
