मान लीजिए कि हमारे पास पूर्णांकों का डेटा स्ट्रीम इनपुट है, ये a1, a2, ..., a, ... की तरह हैं, तो हमें अब तक देखी गई संख्याओं को असंबद्ध अंतरालों की सूची के रूप में सारांशित करना होगा। उदाहरण के लिए, मान लें कि इनपुट पूर्णांक 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 नाम का एक सेट बनाएं
-
प्रारंभकर्ता में, निम्न सेट करें:=-inf और उच्च:=inf
-
AddNum मेथड से जो num को इनपुट के रूप में लेता है, num को सेट nums में डालें
-
अंतराल विधि प्राप्त करें से, निम्न कार्य करें -
-
एक 2डी सरणी रेट परिभाषित करें
-
यह:=सेट अंकों का प्रारंभ तत्व
-
जब तक यह सेट में हो, करें -
-
x :=इसका मान
-
यदि रिट खाली है या रिट + 1
-
रिट के अंत में जोड़ी { x, x } डालें
-
-
अन्यथा
-
रिट के अंतिम तत्व के सूचकांक 1 में मौजूद तत्व को 1 से बढ़ाएं
-
-
इसे अगले तत्व पर
-
-
वापसी रिट
उदाहरण
आइए एक बेहतर समझ प्राप्त करने के लिए निम्नलिखित कार्यान्वयन देखें -
#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());
} इनपुट
Initialize the class, then insert one element at a time and see the intervals. So the elements are [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, ],]