Leetcode 352. 将数据流变为多个不相交区间

题目

给定一个非负整数的数据流输入 a1，a2，…，an，…，将到目前为止看到的数字总结为不相交的区间列表。

例如，假设数据流中的整数为 1，3，7，2，6，…，每次的总结为：

[1, 1] [1, 1], [3, 3] [1, 1], [3, 3], [7, 7] [1, 3], [7, 7] [1, 3], [6, 7]

题解

用一个哈希表记录添加的数，若add了一个已经有的数则不必进行操作；否则，我们先找到大于这个数的第一个区间，有以下几种情况

比第一个区间小 原数组为空，则直接插入如果该值+1等于区间的起始点，则进行合并否则，直接插入 没有区间大于这个数 该值-1等于区间的终止点，则进行合并否则，直接插入 其他情况 该值+1不等于大于它的区间的起始点，该值-1也不等于小于它的区间的终止点，直接插入该值+1等于大于它的区间的起始点，该值-1也等于小于它的区间的终止点，则两个区间进行合并该值+1等于大于它的区间的起始点，该值-1不等于小于它的区间的终止点，则和后区间合并该值+1不等于大于它的区间的起始点，该值-1等于小于它的区间的终止点，则和前区间进行合并 详细过程见代码

代码

class SummaryRanges { public: vector<vector<int>> ans; unordered_map<int,int> use; int size; /** Initialize your data structure here. */ SummaryRanges() { size = 0; } void addNum(int val) { if(use.count(val) != 0) return; use[val] = 1; int i; for(i=0; i<size; i++) if(val < ans[i][0]) break; if(i == 0){ if(size == 0){ ans.insert(ans.begin(),{val,val}); size ++; } else if(val+1 == ans[i][0]) ans[0][0] = val; else{ ans.insert(ans.begin(),{val,val}); size++; } }else if(i == size){ if(val-1 == ans[i-1][1]) ans[i-1][1] = val; else{ ans.push_back({val,val}); size++; } }else{ if(val+1!=ans[i][0] && val-1!=ans[i-1][1]){ ans.insert(ans.begin()+i,{val,val}); size++; }else if(val+1 == ans[i][0] && val-1==ans[i-1][1]){ ans[i-1][1] = ans[i][1]; ans.erase(ans.begin()+i); size--; }else if(val+1 == ans[i][0]){ ans[i][0] = val; }else{ ans[i-1][1] = val; } } } vector<vector<int>> getIntervals() { return ans; } }; /** * Your SummaryRanges object will be instantiated and called as such: * SummaryRanges* obj = new SummaryRanges(); * obj->addNum(val); * vector<vector<int>> param_2 = obj->getIntervals(); */

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/data-stream-as-disjoint-intervals 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。