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

• 题目：352. 将数据流变为多个不相交区间
• • 示例1
  • 提示：
• 解题思路
• • （1）暴力法
  • （2）并查集

难度： 困难

题目：

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

实现 SummaryRanges 类：

SummaryRanges() 使用一个空数据流初始化对象。
void addNum(int val)向数据流中加入整数 val 。
int[][] getIntervals()以不相交区间 [starti, endi] 的列表形式返回对数据流中整数的总结。

输入：
["SummaryRanges", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals"]
[[], [1], [], [3], [], [7], [], [2], [], [6], []]
输出：
[null, null, [[1, 1]], null, [[1, 1], [3, 3]], null, [[1, 1], [3, 3], [7, 7]], null, [[1, 3], [7, 7]], null, [[1, 3], [6, 7]]]

解释：
SummaryRanges summaryRanges = new SummaryRanges();
summaryRanges.addNum(1);      // arr = [1]
summaryRanges.getIntervals(); // 返回 [[1, 1]]
summaryRanges.addNum(3);      // arr = [1, 3]
summaryRanges.getIntervals(); // 返回 [[1, 1], [3, 3]]
summaryRanges.addNum(7);      // arr = [1, 3, 7]
summaryRanges.getIntervals(); // 返回 [[1, 1], [3, 3], [7, 7]]
summaryRanges.addNum(2);      // arr = [1, 2, 3, 7]
summaryRanges.getIntervals(); // 返回 [[1, 3], [7, 7]]
summaryRanges.addNum(6);      // arr = [1, 2, 3, 6, 7]
summaryRanges.getIntervals(); // 返回 [[1, 3], [6, 7]]

• 0 <= val <= 104
• 最多调用 addNum 和 getIntervals 方法 3 * 104 次

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

这题理解题意很关键：addNum输入的数据从0到10000，求出有效的区间。举个例子，输入的数据为[1, 2, 3, 6, 7]，那么getIntervals 输出的区间是：[1, 3]和[6, 7]，也就是连续的数字能够合并，1、2、3合并为[1, 3]，6、7和并为[6, 7]。

所以，我们定义一个10001长度的数组visit[10001]，addNum就将visit[val] = 1;，getIntervals 时从0开始遍历到10001，将满足条件的区间取出即可。

class SummaryRanges {
public:
    int visit[10001];
    SummaryRanges() {
        fill(visit, visit + 10001, 0);
    }
    
    void addNum(int val) {
        visit[val] = true;
    }
    
    vector> getIntervals() {
        vector> ans;
        int start = -1, end = -1;
        for (int i = 0; i < 10001; i++) {
            if (visit[i]) {
                if (start == -1) {
                    start = end = i;
                } else {
                    end++;
                }
            } else {
                if (start != -1) {
                    ans.push_back({start, end});
                    start = end = -1;
                }
            }
        }
        return ans;
    }
};

在暴力法中，因为每次都需要遍历10001次，所以速度很慢。可以通过并查集来优化，比如1、2、3三个元素的father都指向3，然后用set存储元素1，这样遍历set数组，将每个[i, find(i)]加入结果即可。

class SummaryRanges {
public:
    int father[10001];
    set mySet;
    SummaryRanges() {
        fill(father, father + 10001, -1);
    }

    int find(int x) {
        return father[x] == x ? x : father[x] = find(father[x]);
    }
    void Union(int x, int y) {
        if (x >= 0 && x <= 10000 && father[x] != -1 && father[y] != -1) {
            int fx = find(x);
            int fy = find(y);
            if (fx != fy) {
                father[fx] = fy;//小的合并到大的。
                mySet.erase(y);//删除大的
            }
        }
    }
    
    void addNum(int val) {
        if (father[val] == -1) {
            father[val] = val;
            mySet.insert(val);
            Union(val, val + 1);
            Union(val - 1, val);
        }
    }
    
    vector> getIntervals() {
        vector> ans;
        for (auto& num : mySet) {
            ans.push_back({num, find(num)});
        }
        return ans;
    }
};