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

难度:

标签:

题目描述

给你一个由非负整数 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⁴ 次

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

代码结果

运行时间: 30 ms, 内存: 16.7 MB

/*
 * 思路：
 * 使用Stream的方式实现区间合并，主要通过Stream来遍历区间和新数字，
 * 利用filter和map等方法来处理区间合并逻辑。
 */
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.Stream;
 
class SummaryRanges {
    private List<int[]> intervals;
 
    public SummaryRanges() {
        intervals = new ArrayList<>();
    }
 
    public void addNum(int val) {
        List<int[]> newIntervals = new ArrayList<>();
        intervals = Stream.concat(intervals.stream(), Stream.of(new int[]{val, val}))
                .sorted((a, b) -> Integer.compare(a[0], b[0]))
                .collect(Collectors.toList());
        int[] current = intervals.get(0);
        for (int i = 1; i < intervals.size(); i++) {
            int[] next = intervals.get(i);
            if (current[1] + 1 < next[0]) {
                newIntervals.add(current);
                current = next;
            } else {
                current[1] = Math.max(current[1], next[1]);
            }
        }
        newIntervals.add(current);
        intervals = newIntervals;
    }
 
    public int[][] getIntervals() {
        return intervals.toArray(new int[intervals.size()][]);
    }
}

解释

方法:

这个题解使用了并查集的思路。主要的过程如下： 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))

代码细节讲解

🦆

为什么在`addNum`方法中要同时合并`val`与`val+1`以及`val-1`与`val`，这样做的目的是什么？

▷

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

🦆

在`union`方法中，为何选择将一个根节点的父节点设为另一个根节点，而不是相反，这种选择有何依据？

▷

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

🦆

当`val`已经存在于`sortedset`中时，为什么还需要进行合并操作？存在的话是否会进行重复合并？

▷

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

🦆

在`find`函数中进行路径压缩的目的是什么？它如何帮助优化并查集的性能？

▷

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

相关问题

汇总区间

给定一个 无重复元素 的有序整数数组 nums 。

返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表。也就是说，nums 的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个范围但不属于 nums 的数字 x 。

列表中的每个区间范围 [a,b] 应该按如下格式输出：

"a->b" ，如果 a != b
"a" ，如果 a == b

示例 1：

输入：nums = [0,1,2,4,5,7]
输出：["0->2","4->5","7"]
解释：区间范围是：
[0,2] --> "0->2"
[4,5] --> "4->5"
[7,7] --> "7"

示例 2：

输入：nums = [0,2,3,4,6,8,9]
输出：["0","2->4","6","8->9"]
解释：区间范围是：
[0,0] --> "0"
[2,4] --> "2->4"
[6,6] --> "6"
[8,9] --> "8->9"

提示：

0 <= nums.length <= 20
-2³¹ <= nums[i] <= 2³¹ - 1
nums 中的所有值都 互不相同
nums 按升序排列

寻找右区间

给你一个区间数组 intervals ，其中 intervals[i] = [start_i, end_i] ，且每个 start_i 都不同。

区间 i 的 右侧区间 可以记作区间 j ，并满足 start_j >= end_i ，且 start_j 最小化 。注意 i 可能等于 j 。

返回一个由每个区间 i 的 右侧区间 在 intervals 中对应下标组成的数组。如果某个区间 i 不存在对应的 右侧区间 ，则下标 i 处的值设为 -1 。

示例 1：

输入：intervals = [[1,2]]
输出：[-1]
解释：集合中只有一个区间，所以输出-1。

示例 2：

输入：intervals = [[3,4],[2,3],[1,2]]
输出：[-1,0,1]
解释：对于 [3,4] ，没有满足条件的“右侧”区间。
对于 [2,3] ，区间[3,4]具有最小的“右”起点;
对于 [1,2] ，区间[2,3]具有最小的“右”起点。

示例 3：

输入：intervals = [[1,4],[2,3],[3,4]]
输出：[-1,2,-1]
解释：对于区间 [1,4] 和 [3,4] ，没有满足条件的“右侧”区间。
对于 [2,3] ，区间 [3,4] 有最小的“右”起点。

提示：

1 <= intervals.length <= 2 * 10⁴
intervals[i].length == 2
-10⁶ <= start_i <= end_i <= 10⁶
每个间隔的起点都 不相同

Range 模块

Range模块是跟踪数字范围的模块。设计一个数据结构来跟踪表示为 半开区间 的范围并查询它们。

半开区间 [left, right) 表示所有 left <= x < right 的实数 x 。

实现 RangeModule 类:

RangeModule() 初始化数据结构的对象。
void addRange(int left, int right) 添加 半开区间 [left, right)，跟踪该区间中的每个实数。添加与当前跟踪的数字部分重叠的区间时，应当添加在区间 [left, right) 中尚未跟踪的任何数字到该区间中。
boolean queryRange(int left, int right) 只有在当前正在跟踪区间 [left, right) 中的每一个实数时，才返回 true ，否则返回 false 。
void removeRange(int left, int right) 停止跟踪 半开区间 [left, right) 中当前正在跟踪的每个实数。

示例 1：

输入
["RangeModule", "addRange", "removeRange", "queryRange", "queryRange", "queryRange"]
[[], [10, 20], [14, 16], [10, 14], [13, 15], [16, 17]]
输出
[null, null, null, true, false, true]

解释
RangeModule rangeModule = new RangeModule();
rangeModule.addRange(10, 20);
rangeModule.removeRange(14, 16);
rangeModule.queryRange(10, 14); 返回 true （区间 [10, 14) 中的每个数都正在被跟踪）
rangeModule.queryRange(13, 15); 返回 false（未跟踪区间 [13, 15) 中像 14, 14.03, 14.17 这样的数字）
rangeModule.queryRange(16, 17); 返回 true （尽管执行了删除操作，区间 [16, 17) 中的数字 16 仍然会被跟踪）

提示：

1 <= left < right <= 10⁹
在单个测试用例中，对 addRange 、 queryRange 和 removeRange 的调用总数不超过 10⁴ 次

安卓系统手势解锁贪吃蛇