题目描述

给定一个非负整数的数据流输入 $a_1, a_2, \dots, a_n, \dots$，将到目前为止看到的数字总结为不相交的区间列表。

例如，假设数据流中的整数为 $1, 3, 7, 2, 6, \dots$，每次的总结为：

[1, 1]
[1, 1], [3, 3]
[1, 1], [3, 3], [7, 7]
[1, 3], [7, 7]
[1, 3], [6, 7]

进阶

• 如果有很多合并，并且与数据流的大小相比，不相交区间的数量很小，该怎么办？

算法

(有序集 + 并查集) 插入 $O(\log n)$；查询 $O(m)$。

1. 设计三种数据结构，set<int> num 存储当前数据的有序集合，unordered_map<int, int> f 相当于并查集的数组，unordered_map<int, set<int>::iterator> hash 记录每个数字在有序集合中的迭代器。
2. 新插入一个数字时，更新有序集合和有序集合的哈希表。然后把当前数字 x 看成 x 和 x + 1，并且 x 为根的子树要合并到以 x + 1 为根的子树（注意合并的方向，一定是 x 往 x + 1 上合并）。
3. 查询时，从有序集中的最小元素开始。当前元素为 x，通过并查集找到 x 的根 fx，则 [x, fx - 1] 就是一个区间。然后 x 更新为 fx - 1 所在迭代器的下一个位置。

时间复杂度

• 插入时，更新有序集合的时间复杂度为 $O(\log n)$，并查集的合并时间复杂度近似为常数。
• 查询时，由于并查集的查询时间近似为常数，所以时间复杂度等于不相交区间的数量 $m$。

空间复杂度

• 每一个数字都要占用空间，故总的空间复杂度为 $O(n)$。

C++ 代码

class SummaryRanges {
public:
    /** Initialize your data structure here. */
    set<int> num;
    unordered_map<int, int> f;
    unordered_map<int, set<int>::iterator> hash;

    SummaryRanges() {

    }

    void addNum(int val) {
        int x = val, y = val + 1;
        num.insert(x);
        hash[x] = num.find(x);

        if (f.find(x) == f.end()) f[x] = x;
        if (f.find(y) == f.end()) f[y] = y;

        if (find(x) != find(y))
            f[f[x]] = f[y];
    }

    vector<vector<int>> getIntervals() {
        vector<vector<int>> ans;

        auto x = num.begin();

        while (x != num.end()) {
            int fx = find(*x);
            ans.push_back({*x, fx - 1});
            x = hash[fx - 1];
            x++;
        }

        return ans;
    }

private:
    int find(int x) {
        return x == f[x] ? x : f[x] = find(f[x]);
    }
};

/**
 * Your SummaryRanges object will be instantiated and called as such:
 * SummaryRanges* obj = new SummaryRanges();
 * obj->addNum(val);
 * vector<vector<int>> param_2 = obj->getIntervals();
 */