链接将数据流变为多个不相交区间352. 将数据流变为多个不相交区间 - 力扣LeetCode题解一、set方法add是log(n)get是O(n)因为需要遍历并查集构造vector1、通过set维护排序2、upper_bound找到第一个val的位置3.分情况讨论a.然后判断当前位置的前一个元素判断前面的区间是否包含val需要注意前面的区间是否存在b.判断前面的区间的last1 val如果okstart前面区间的begin。删除前面的ite_prevc.判断后面的区间的fist-1 val, 如果okend后面区间的last。删除ited.插入新的区间使用prev需要判断容器是否为empty二、并查集union findadd是O(1)get是nlog(n)需要排序add时候判断当前val是否是新元素是新元素初始化下father和intervals判断val-1和val1是否存在如果存在则merge 一下fahter和intervals三、数组add时间复杂度是最坏O(n)最好是O(long(n))get是O(1)add时候可以用二分找到第一个 val的位置分情况讨论判断left和right是否都可以合并class Solution { public: void addNum(int val) { // 空容器直接插入 if (_intervals.empty()) { _intervals.insert({val, val}); return; } // 找到第一个 start val 的区间 auto bigger_ite _intervals.upper_bound({val, INT_MAX}); // 检查是否已经在某个区间内与前一个区间比较 if (bigger_ite ! _intervals.begin()) { auto ite_prev prev(bigger_ite); if (val ite_prev-second) { return; // 已经在区间内无需操作 } } bool connect_left false; bool connect_right false; int start val; int end val; // 判断与左区间是否相邻 if (bigger_ite ! _intervals.begin()) { auto ite_prev prev(bigger_ite); if (ite_prev-second 1 val) { connect_left true; start ite_prev-first; _intervals.erase(ite_prev); } } // 判断与右区间是否相邻 if (bigger_ite ! _intervals.end()) { if (bigger_ite-first - 1 val) { connect_right true; end bigger_ite-second; _intervals.erase(bigger_ite); } } _intervals.insert({start, end}); } vectorInterval getIntervals() { vectorInterval result; for (auto entry : _intervals) { result.push_back(Interval(entry.first, entry.second)); } return result; // 关键必须返回 } private: setpairint, int _intervals; };/** * Definition of Interval: * classs Interval { * int start, end; * Interval(int start, int end) { * this-start start; * this-end end; * } * } */ class Solution { public: /** * param val: An integer. * return: nothing */ void addNum(int val) { // write your code here auto bigger_ite _intervals.upper_bound({val, INT_MAX}); // 判断val是否在当前区间内 auto ite_prev bigger_ite _intervals.end() ? _intervals.end() : prev(bigger_ite); if (ite_prev ! _intervals.end() val ite_prev-first val ite_prev-second) { return; } // 判断和前面是否合并 bool connect_left (ite_prev ! _intervals.end() ite_prev-second 1 val); bool connect_right (bigger_ite ! _intervals.end() bigger_ite-first - 1 val); int start val; int end val; if (connect_left) { start ite_prev-first; _intervals.erase(ite_prev); } if (connect_right) { end bigger_ite-second; _intervals.erase(bigger_ite); } _intervals.insert(pairint, int(start, end)); } /** * return: A list of intervals. */ vectorInterval getIntervals() { // write your code here if (_intervals.size() 0) { return {}; } vectorInterval result; result.reserve(_intervals.size()); for (auto entry : _intervals) { Interval tmp(entry.first, entry.second); result.push_back(move(tmp)); } return result; } setpairint, int _intervals; };/** * Definition of Interval: * classs Interval { * int start, end; * Interval(int start, int end) { * this-start start; * this-end end; * } * } */ class Solution { public: /** * param val: An integer. * return: nothing */ void addNum(int val) { // write your code here auto bigger_ite _intervals.upper_bound({val, INT_MAX}); // 判断val是否在当前区间内 auto ite_prev bigger_ite _intervals.begin() ? _intervals.end() : prev(bigger_ite); if (ite_prev ! _intervals.end() val ite_prev-second) { return; } // 判断和前面是否合并 bool connect_left (ite_prev ! _intervals.end() ite_prev-second 1 val); bool connect_right (bigger_ite ! _intervals.end() bigger_ite-first - 1 val); int start val; int end val; if (connect_left) { start ite_prev-first; _intervals.erase(ite_prev); } if (connect_right) { end bigger_ite-second; _intervals.erase(bigger_ite); } _intervals.insert(pairint, int(start, end)); } /** * return: A list of intervals. */ vectorInterval getIntervals() { // write your code here if (_intervals.size() 0) { return {}; } vectorInterval result; result.reserve(_intervals.size()); for (auto entry : _intervals) { Interval tmp(entry.first, entry.second); result.push_back(move(tmp)); } return result; } setpairint, int _intervals; };/** * Definition of Interval: * classs Interval { * int start, end; * Interval(int start, int end) { * this-start start; * this-end end; * } * } */ class Solution { public: /** * param val: An integer. * return: nothing */ void addNum(int val) { // write your code here if (_father.find(val) ! _father.end()) { return; } _father[val] val; _intervals[val] pairint, int(val, val); if (_father.find(val - 1) ! _father.end()) { merge(val - 1, val); } if (_father.find(val 1) ! _father.end()) { merge(val, val 1); } } /** * return: A list of intervals. */ vectorInterval getIntervals() { // write your code here int len _father.size(); if (len 0) { return {}; } vectorInterval result; result.reserve(len); for (auto e : _father) { if (e.first e.second) { Interval tmp(_intervals[e.first].first, _intervals[e.first].second); result.push_back(move(tmp)); } } sort(result.begin(), result.end(), [](Interval a, Interval b) { return a.start b.start; }); return result; } void merge(int a, int b) { int fa find(a); int fb find(b); if (fa ! fb) { _father[fa] fb; // cout a b fb : fb endl; _intervals[fb].first min(_intervals[fb].first, _intervals[fa].first); _intervals[fb].second max(_intervals[fb].second, _intervals[fa].second); } } int find(int a) { while (_father[a] ! a) { a _father[a]; } return a; } unordered_mapint, int _father; unordered_mapint, pairint, int _intervals; };class SummaryRanges { public: SummaryRanges() { } void addNum(int val) { // 二分找到第一个起点 val 的位置 int lo 0, hi intervals.size(); while (lo hi) { int mid lo (hi - lo) / 2; if (intervals[mid][0] val) { lo mid 1; } else { hi mid; } } int idx lo; // 第一个起点 val 的区间下标 // 1. 是否被左邻居覆盖 if (idx 0 intervals[idx - 1][1] val) { return; } // 2. 判断能否与左邻居 / 右邻居合并 bool mergeLeft (idx 0 intervals[idx - 1][1] 1 val); bool mergeRight (idx (int)intervals.size() intervals[idx][0] val 1); if (mergeLeft mergeRight) { // 同时合并左右两个区间 intervals[idx - 1][1] intervals[idx][1]; intervals.erase(intervals.begin() idx); } else if (mergeLeft) { intervals[idx - 1][1] val; } else if (mergeRight) { intervals[idx][0] val; } else { // 插入独立区间 intervals.insert(intervals.begin() idx, {val, val}); } } vectorvectorint getIntervals() { return intervals; } private: vectorvectorint intervals; // 按区间起点升序 }; /** * Your SummaryRanges object will be instantiated and called as such: * SummaryRanges* obj new SummaryRanges(); * obj-addNum(value); * vectorvectorint param_2 obj-getIntervals(); */class SummaryRanges { public: SummaryRanges() {} void addNum(int value) { if (_intervals.empty()) { _intervals.push_back({value, value}); return; } int index upper_bound(value); //cout index: index endl; int prev_index index - 1 0 ? index - 1 : -1; if (prev_index ! -1 _intervals[prev_index][1] value) { return; } bool merge_left prev_index ! -1 _intervals[prev_index][1] 1 value ? true : false; bool merge_right index _intervals.size() _intervals[index][0] - 1 value ? true : false; if (merge_left merge_right) { _intervals[prev_index][1] _intervals[index][1]; _intervals.erase(_intervals.begin() index); } else if (merge_left) { _intervals[prev_index][1] value; } else if (merge_right) { _intervals[index][0] value; } else { vectorint tmp{value, value}; _intervals.insert(_intervals.begin() index, tmp); } } int upper_bound(int value) { int left 0; int right _intervals.size() - 1; while (left 1 right) { int mid left (right - left) / 2; if (_intervals[mid][0] value) { right mid; } else if (_intervals[mid][0] value) { left mid; } else { right mid; } } if (_intervals[left][0] value) { return left; } if (_intervals[right][0] value) { return right; } return _intervals.size(); } vectorvectorint getIntervals() { return _intervals; } vectorvectorint _intervals; }; /** * Your SummaryRanges object will be instantiated and called as such: * SummaryRanges* obj new SummaryRanges(); * obj-addNum(value); * vectorvectorint param_2 obj-getIntervals(); */