企业官网建设流程全解析

链接：将数据流变为多个不相交区间

352. 将数据流变为多个不相交区间 - 力扣（LeetCode）

题解：

一、set方法

add是log(n)

get是O(n)因为需要，遍历并查集，构造vector

1、通过set维护排序

2、upper_bound找到第一个>val的位置

3.分情况讨论

a.然后判断当前位置的前一个元素，判断前面的区间是否包含val（需要注意前面的区间是否存在）

b.判断前面的区间的last+1 == val，如果ok，start=前面区间的begin。删除前面的ite_prev

c.判断后面的区间的fist-1 == val, 如果ok，end=后面区间的last。删除ite

d.插入新的区间

使用prev需要判断，容器是否为empty

二、并查集union find

add是O(1)

get是nlog(n)需要排序

add时候判断当前val，是否是新元素，是新元素初始化下father和intervals

判断val-1和val+1是否存在，如果存在则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}); } vector<Interval> getIntervals() { vector<Interval> result; for (auto& entry : _intervals) { result.push_back(Interval(entry.first, entry.second)); } return result; // 关键：必须返回 } private: set<pair<int, 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(pair<int, int>(start, end)); } /** * @return: A list of intervals. */ vector<Interval> getIntervals() { // write your code here if (_intervals.size() <= 0) { return {}; } vector<Interval> result; result.reserve(_intervals.size()); for (auto& entry : _intervals) { Interval tmp(entry.first, entry.second); result.push_back(move(tmp)); } return result; } set<pair<int, 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(pair<int, int>(start, end)); } /** * @return: A list of intervals. */ vector<Interval> getIntervals() { // write your code here if (_intervals.size() <= 0) { return {}; } vector<Interval> result; result.reserve(_intervals.size()); for (auto& entry : _intervals) { Interval tmp(entry.first, entry.second); result.push_back(move(tmp)); } return result; } set<pair<int, 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] = pair<int, 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. */ vector<Interval> getIntervals() { // write your code here int len = _father.size(); if (len <= 0) { return {}; } vector<Interval> 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_map<int, int> _father; unordered_map<int, pair<int, 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}); } } vector<vector<int>> getIntervals() { return intervals; } private: vector<vector<int>> intervals; // 按区间起点升序 }; /** * Your SummaryRanges object will be instantiated and called as such: * SummaryRanges* obj = new SummaryRanges(); * obj->addNum(value); * vector<vector<int>> 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 { vector<int> 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(); } vector<vector<int>> getIntervals() { return _intervals; } vector<vector<int>> _intervals; }; /** * Your SummaryRanges object will be instantiated and called as such: * SummaryRanges* obj = new SummaryRanges(); * obj->addNum(value); * vector<vector<int>> param_2 = obj->getIntervals(); */