首页 > 代码库 > [leetcode]352. Data Stream as Disjoint Intervals
[leetcode]352. Data Stream as Disjoint Intervals
数据流合并成区间，每次新来一个数，表示成一个区间，然后在已经保存的区间中进行二分查找，最后结果有3种，插入头部，尾部，中间，插入头部，不管插入哪里，都判断一下左边和右边是否能和当前的数字接起来，我这样提交了，发现错了，想到之前考虑要不要判重，我感觉是这个问题，然后就是在二分查找的时候，判断一下左右区间是否包含当前的值，包含就直接返回。
1 /** 2 * Definition for an interval. 3 * struct Interval { 4 * int start; 5 * int end; 6 * Interval() : start(0), end(0) {} 7 * Interval(int s, int e) : start(s), end(e) {} 8 * }; 9 */10 bool cmp(Interval a, Interval b) {11 if(a.start == b.start) return a.end < b.end;12 return a.start < b.start;13 }14 class SummaryRanges {15 public:16 /** Initialize your data structure here. */17 18 vector<Interval> v;19 SummaryRanges() {20 v.clear();21 }22 23 void addNum(int val) {24 //cout << val << " " << v.size() << endl;25 Interval d(val, val);26 if(v.size() == 0) v.push_back(d);27 else {28 int t = lower_bound(v.begin(), v.end(), d, cmp) - v.begin();29 //cout << val << " " << t << endl;30 if(t == 0) {31 if(val == v[0].start) return;32 if(v[0].start - 1 == val) {33 v[0].start = val;34 } else {35 v.insert(v.begin() + t, d);36 }37 } else if(t == v.size()) {38 if(v[t - 1].end >= val) return;39 if(v[t - 1].end + 1 == val) {40 v[t - 1].end = val;41 } else {42 v.push_back(d);43 }44 } else {45 if(v[t - 1].start == val || v[t - 1].end >= val || v[t].start == val) return;46 if(v[t - 1].end + 2 == v[t].start) {47 v[t - 1].end = v[t].end;48 v.erase(v.begin() + t);49 } else if(v[t - 1].end + 1 == val) {50 v[t - 1].end = val;51 } else if(v[t].start - 1 == val) {52 v[t].start = val;53 } else {54 v.insert(v.begin() + t, d);55 }56 }57 58 }59 }60 61 vector<Interval> getIntervals() {62 return v;63 }64 };65 66 /**67 * Your SummaryRanges object will be instantiated and called as such:68 * SummaryRanges obj = new SummaryRanges();69 * obj.addNum(val);70 * vector<Interval> param_2 = obj.getIntervals();71 */
[leetcode]352. Data Stream as Disjoint Intervals
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。