产品外观设计网站,网站程序模块,容城县建设银行网站,湛江网站建设公司文章目录1. 题目2. 解题1. 题目
给定一个非负整数的数据流输入 a1#xff0c;a2#xff0c;…#xff0c;an#xff0c;…#xff0c;将到目前为止看到的数字总结为不相交的区间列表。
例如#xff0c;假设数据流中的整数为 1#xff0c;3#xff0c;7#xff0c;2a2…an…将到目前为止看到的数字总结为不相交的区间列表。
例如假设数据流中的整数为 13726…每次的总结为
[1, 1]
[1, 1], [3, 3]
[1, 1], [3, 3], [7, 7]
[1, 3], [7, 7]
[1, 3], [6, 7]进阶 如果有很多合并并且与数据流的大小相比不相交区间的数量很小该怎么办? 来源力扣LeetCode 链接https://leetcode-cn.com/problems/data-stream-as-disjoint-intervals 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
题目不难二分查找 if else 就可以了看找到的位置前后能否合并见注释
class SummaryRanges {mapint,int m; // start, end
public:/** Initialize your data structure here. */SummaryRanges() {}void addNum(int val) {if(m.empty()){m[val] val;return;}auto it m.lower_bound(val); // it 的 start valif(it ! m.end()) // 后面有区间{int start it-first;int end it-second;if(start val)return;else if(start val1) // val 可以 跟 it 区间合并{if(it ! m.begin()) // it 前面还有区间{it--;int prevStart it-first;int prevEnd it-second;if(prevEnd1 val) // val 可以跟前面合并{m.erase(start);//删除后面区间m[prevStart] end;//两个区间合并}else//不能跟前面合并{m.erase(start);m[val] end;//更新后面的区间}}else//前面没有区间{m.erase(start);m[val] end;//更新后面的区间}}else // val 不可以 跟 it 区间合并{if(it ! m.begin()) // it 前面还有区间{it--;int prevStart it-first;int prevEnd it-second;if(prevEnd1 val){ // val 可以跟前面合并m[prevStart] val;}else if(prevEnd1 val){ // 前后都不能合并自己独立m[val] val;}}else{m[val] val;}}}else // 后面没有区间{it--;int prevStart it-first;int prevEnd it-second;if(prevEnd1 val){ // 可以跟前面合并m[prevStart] val;}else if(prevEnd1 val)m[val] val;//不能合并独立}}vectorvectorint getIntervals() {vectorvectorint ans(m.size());int i 0;for(auto mi : m){ans[i] {mi.first, mi.second};}return ans;}
};56 ms 29.1 MB C
题解区还有比较暴力的做法直接全部插入set最后顺序整理区间
class SummaryRanges {
public:/** Initialize your data structure here. */setint ans;SummaryRanges() {}void addNum(int val) {ans.insert(val);}vectorvectorint getIntervals() {vectorvectorint res;int left *ans.begin();int right *ans.begin();for (auto it ans.begin(); it ! ans.end(); it) {if (*it right 1) {res.push_back({left, right});left *it;}right *it;}res.push_back({left, right});return res;}
};作者qia-si-ming-yue-qing-feng
链接https://leetcode-cn.com/problems/data-stream-as-disjoint-intervals/solution/bao-li-mei-xue-setyong-fa-by-qia-si-ming-yue-qing-/
来源力扣LeetCode
著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。其时间 96 ms 31.7 MB C我的解法稍优一些 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
