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

难度: Hard

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

实现 SummaryRanges 类：

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

示例：

输入：
["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 <= 10⁴
最多调用 addNum 和 getIntervals 方法 3 * 10⁴ 次

进阶：如果存在大量合并，并且与数据流的大小相比，不相交区间的数量很小，该怎么办?

Submission

运行时间: 30 ms

内存: 16.7 MB

from typing import List

# class SummaryRanges:
#     def __init__(self):

#     def addNum(self, val: int) -> None:

#     def getIntervals(self) -> List[List[int]]:


class SummaryRanges:
    def __init__(self):
        self.parent = [-1] * MAXNUM
        self.sortedset = SortedSet()

    def find(self, x):
        if x != self.parent[x]:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        if (
            0 <= x < MAXNUM
            and 0 <= y < MAXNUM
            and self.parent[x] != -1
            and self.parent[y] != -1
        ):
            x = self.find(x)
            y = self.find(y)
            if x != y:
                self.parent[x] = y

    def addNum(self, val: int) -> None:
        if self.parent[val] == -1:
            self.parent[val] = val
            self.sortedset.add(val)
            self.union(val, val + 1)
            self.union(val - 1, val)

    def getIntervals(self) -> List[List[int]]:
        res = []
        for s in self.sortedset:
            if res and res[-1][-1] >= s:
                continue
            e = self.find(s)
            res.append([s, e])
        return res


MAXNUM = 10001

from sortedcontainers import SortedSet

# 并查集
# class SummaryRanges:
#     def __init__(self):
#         self.parent = [-1] * 10001
#         self.set = SortedSet()

#     def find(self, x):
#         if x != self.parent[x]:
#             self.parent[x] = self.find(self.parent[x])
#         return self.parent[x]

#     def uion(self, x, y):
#         if (
#             0 <= x < MAXNUM
#             and 0 <= y < MAXNUM
#             and self.parent[x] != -1
#             and self.parent[y] != -1
#         ):
#             x = self.find(x)
#             y = self.find(y)
#             if x != y:
#                 self.parent[x] = y
#                 # if y in self.set:
#                 #     self.set.remove(y)

#     def addNum(self, val: int) -> None:
#         if self.parent[val] == -1:
#             self.parent[val] = val
#             self.set.add(val)
#             self.uion(val, val + 1)
#             self.uion(val - 1, val)

#     def getIntervals(self) -> List[List[int]]:
#         res = []
#         for s in self.set:
#             if res and res[-1][1] >= s:
#                 continue
#             e = self.find(s)
#             res.append([s, e])
#         return res

#     # def getIntervals(self) -> List[List[int]]:
#     #     i = 0
#     #     res = []
#     #     while i < MAXNUM:
#     #         if self.parent[i] != -1:
#     #             start = i
#     #             end = self.find(i)
#     #             res.append([start, end])
#     #             i = end + 1
#     #         else:
#     #             i += 1

#     #     return res


# class SummaryRanges:
#     def __init__(self):
#         self.parent = [-1] * 10001

#     def find(self, x):
#         if self.parent[x] != x:
#             self.parent[x] = self.find(self.parent[x])
#         return self.parent[x]

#     def union(self, x, y):
#         if (
#             0 <= x <= 10000
#             and 0 <= y <= 10000
#             and self.parent[x] != -1
#             and self.parent[y] != -1
#         ):
#             x = self.find(x)
#             y = self.find(y)
#             if x != y:
#                 self.parent[x] = y

#     def addNum(self, val: int) -> None:
#         if self.parent[val] == -1:
#             self.parent[val] = val
#             self.union(val, val + 1)
#             self.union(val - 1, val)

#     def getIntervals(self) -> List[List[int]]:
#         i = 0
#         res = []
#         while i < 10001:
#             if self.parent[i] != -1:
#                 start = i
#                 end = self.find(i)
#                 res.append([start, end])
#                 i = end + 1
#             else:
#                 i += 1
#         return res


# 二分法
# class SummaryRanges:
#     def __init__(self):
#         head = [-10, -10]
#         tail = [10010, 10010]
#         self.list = [head, tail]

#     def addNum(self, val: int) -> None:
#         n = len(self.list)
#         l, r = 0, n - 1
#         while l < r:
#             m = (l + r + 1) >> 1 # l=mid，r=mid-1的二分
#             if self.list[m][0] <= val:
#                 l = m
#             else:
#                 r = m - 1

#         tmp = [val, val]
#         prev = self.list[r]
#         next = self.list[r + 1]
#         if prev[0] <= val <= prev[1] or next[0] <= val <= next[1]:
#             pass
#         elif prev[1] + 1 == val and next[0] - 1 == val:
#             prev[1] = next[1]
#             self.list.pop(r + 1)
#         elif prev[1] + 1 == val:
#             prev[1] = val
#         elif next[0] - 1 == val:
#             next[0] = val
#         else:
#             self.list.insert(r + 1, tmp)

#     def getIntervals(self) -> List[List[int]]:
#         return self.list[1:-1]


# Your SummaryRanges object will be instantiated and called as such:
# obj = SummaryRanges()
# obj.addNum(value)
# param_2 = obj.getIntervals()

Explain

这个题解使用了并查集的思路。主要的过程如下： 1. 初始化一个大小为 MAXNUM 的数组 parent，初始值都为 -1，表示每个数都是一个独立的集合。同时初始化一个有序集合 sortedset 用于存储加入的数字。 2. 当添加一个新的数字 val 时，首先判断 parent[val] 是否为 -1，如果是则将其加入 sortedset，并将 parent[val] 设为 val。然后将 val 与 val-1 和 val+1 进行合并操作。 3. 合并操作使用 union 函数，它首先判断两个数是否都在合法范围内且都已经加入过，然后分别找到它们的根节点，如果根节点不同则将其中一个根节点的父节点设为另一个根节点，相当于将两个集合合并。 4. 当需要获取区间列表时，遍历 sortedset，对于每个数字 s，如果它与前一个区间的右端点重合则跳过，否则找到 s 的根节点 e，将 [s,e] 加入结果列表。

时间复杂度: addNum: O(logN), getIntervals: O(NlogN), 其中 N 为数据流中的数字个数。

空间复杂度: O(max(MAXNUM, N))

```python
from typing import List
from sortedcontainers import SortedSet

MAXNUM = 10001

class SummaryRanges:
    def __init__(self):
        self.parent = [-1] * MAXNUM  # 初始化 parent 数组，初始值为 -1
        self.sortedset = SortedSet()  # 初始化有序集合

    def find(self, x):
        if x != self.parent[x]:  # 如果 x 不是根节点
            self.parent[x] = self.find(self.parent[x])  # 递归查找根节点并进行路径压缩
        return self.parent[x]  # 返回根节点

    def union(self, x, y):
        if (
            0 <= x < MAXNUM
            and 0 <= y < MAXNUM
            and self.parent[x] != -1
            and self.parent[y] != -1
        ):  # 判断 x 和 y 是否都在合法范围内且都已加入过
            x = self.find(x)  # 找到 x 的根节点
            y = self.find(y)  # 找到 y 的根节点
            if x != y:  # 如果 x 和 y 的根节点不同
                self.parent[x] = y  # 将 x 的根节点的父节点设为 y 的根节点，相当于将 x 所在集合合并到 y 所在集合

    def addNum(self, val: int) -> None:
        if self.parent[val] == -1:  # 如果 val 是第一次加入
            self.parent[val] = val  # 将 val 的父节点设为自身
            self.sortedset.add(val)  # 将 val 加入有序集合
            self.union(val, val + 1)  # 将 val 与 val+1 合并
            self.union(val - 1, val)  # 将 val-1 与 val 合并

    def getIntervals(self) -> List[List[int]]:
        res = []  # 初始化结果列表
        for s in self.sortedset:  # 遍历有序集合中的数字
            if res and res[-1][-1] >= s:  # 如果当前数字与前一个区间的右端点重合
                continue  # 跳过
            e = self.find(s)  # 找到当前数字的根节点，即区间的右端点
            res.append([s, e])  # 将区间加入结果列表
        return res
```

Explore

在`addNum`方法中同时合并`val`与`val+1`以及`val-1`与`val`的目的是为了维护和更新区间的连续性。当添加一个新的数字`val`时，如果`val+1`或`val-1`已存在于数据结构中，这意味着`val`可以与这些数字连成一个更大的区间。通过合并操作，我们确保每个连续区间都被合并为一个集合，使得后续可以更容易地查询和管理这些区间。

在`union`方法中，选择将一个根节点的父节点设为另一个根节点通常是基于启发式策略，如按秩合并或路径压缩，来优化并查集的性能。在这个特定的实现中，并没有明确指出使用这些优化策略，因此选择哪个作为父节点可能是任意的。然而，在实际应用中，通常会选择将较小树的根节点指向较大树的根节点，以减少查找时间。

如果`val`已经存在于`sortedset`中，理论上表示该值已经被处理过且其所属区间已经建立。此时，进行`val`与`val+1`或`val-1`的合并操作通常是为了处理边界情况，例如当后来加入的数字填补了原有区间之间的空隙时。如果`val`已经存在，`val`的合并操作应该不会执行，因为并查集中已经有`val`的信息，且在`addNum`中有先检查`parent[val]`是否为`-1`的步骤，确保不会对已存在的值进行重复合并。

在`find`函数中进行路径压缩的目的是减少树的高度，从而加快查找根节点的速度。路径压缩通过使路径上的每个节点直接指向其根节点来实现。这样，后续的查找操作将更快，因为可以减少必须经过的中间节点。路径压缩是一种有效的优化手段，可以显著降低并查集操作的平均时间复杂度，从而提高整体性能。