假设我们有一个整数的数据流输入,这些整数就像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设置为
从以num作为输入的addNum方法中,将num插入设置的nums中。
从获取间隔方法中,执行以下操作-
定义一个2D阵列ret
它:=设置数字的开始元素
当它在集合中时,请-
将ret的最后一个元素的索引1处的元素增加1
在ret的末尾插入对{x,x}
x:=它的值
如果ret为空或元素位于ret的最后一个元素的索引1 + 1 <x,则,
除此以外
它到下一个元素
返回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()); }
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, ],]