★ FEATURED ARTICLE 教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本篇技术指南基于 AlgoNote 算法通关手册中 0352. 将数据流变为多个不相交区间 的题解深入讲解如何设计一个SummaryRanges类把动态输入的非负整数数据流实时总结为不相交区间列表。读完本篇你将掌握「哈希集合去重 排序后线性扫描合并区间」的经典设计思路、对应的完整可运行 Python 实现并能理解其在大量合并、区间数量稀少场景下的优化方向。一、题目回顾数据流与不相交区间描述给定一个由非负整数 $a1, a2, ..., an$ 组成的数据流输入需要将到目前为止看到的数字总结为不相交的区间列表。要求实现SummaryRanges类SummaryRanges()使用一个空数据流初始化对象。void addNum(int val)向数据流中加入整数 $val$。int[][] getIntervals()以不相交区间 $[start_i, end_i]$ 的列表形式返回对数据流中整数的总结。说明$0 \le val \le 10^{4}$。最多调用addNum和getIntervals方法 $3 \times 10^{4}$ 次。进阶如果存在大量合并并且与数据流的大小相比不相交区间的数量很小该怎么办示例输入 [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]]从示例可以直观看出关键规律数字1、2、3连续合并为[1, 3]数字6、7连续合并为[6, 7]。所谓「不相交区间」本质就是值域上连续的一段整数这正是本仓库中「区间类问题」一贯的处理对象。二、解题思路集合 动态生成区间这道题的核心是维护一个数字集合然后在需要时动态生成不相交的区间列表。其标签为「设计、二分查找、有序集合」在本题解中我们先从最简单、最易于验证正确性的「集合 动态生成」方案讲起。2.1 算法思路数据结构选择使用集合set存储所有出现过的数字利用集合的去重特性自动处理重复数字——同一个数字多次addNum只保留一份不会影响区间划分。添加数字当添加数字 $val$ 时直接将其加入集合中时间复杂度为 $O(1)$。获取区间当需要获取区间列表时将集合中的所有数字排序。遍历排序后的数字连续的数字合并为一个区间。遇到不连续的数字时开始新的区间。2.2 具体步骤使用集合存储所有添加的数字。addNum(val)将 $val$ 添加到集合中。getIntervals()对集合中的数字排序得到 $sorted_nums$。初始化 $start end sorted_nums[0]$。遍历剩余数字如果 $sorted_nums[i] end 1$则扩展当前区间 $end sorted_nums[i]$。否则保存当前区间 $[start, end]$开始新区间 $start end sorted_nums[i]$。最后添加最后一个区间。这一「排序 → 扫描 → 按连续性切分」的流程与仓库中 0228. 汇总区间 的「双指针」思路同源后者对静态有序数组用nums[j 1] nums[j] 1判断连续性前者对动态无序集合先排序再判断sorted_nums[i] end 1两者共用同一个核心不变量——后一个数恰好比前一个数大 1 时合并。2.3 代码class SummaryRanges: def __init__(self): # 使用集合存储所有出现过的数字 self.nums set() def addNum(self, value: int) - None: # 将数字添加到集合中集合自动去重 self.nums.add(value) def getIntervals(self) - List[List[int]]: # 如果集合为空返回空列表 if not self.nums: return [] # 将集合中的数字排序 sorted_nums sorted(self.nums) intervals [] # 初始化第一个区间 start end sorted_nums[0] # 遍历剩余数字构建区间 for i in range(1, len(sorted_nums)): if sorted_nums[i] end 1: # 当前数字与前一个数字连续扩展当前区间 end sorted_nums[i] else: # 当前数字与前一个数字不连续保存当前区间并开始新区间 intervals.append([start, end]) start end sorted_nums[i] # 添加最后一个区间 intervals.append([start, end]) return intervals # Your SummaryRanges object will be instantiated and called as such: # obj SummaryRanges() # obj.addNum(value) # param_2 obj.getIntervals()2.4 复杂度分析时间复杂度addNum(val)$O(1)$集合的插入操作时间复杂度为常数。getIntervals()$O(n \log n)$其中 $n$ 为集合中数字的个数主要时间消耗在排序上。空间复杂度$O(n)$其中 $n$ 为添加的不同数字的个数。三、进阶场景剖析大量合并、区间稀少时怎么办原题给出了一条进阶问题如果存在大量合并并且与数据流的大小相比不相交区间的数量很小该怎么办先分析上面「集合 动态生成」方案在进阶场景下的瓶颈getIntervals()每次都要对整个集合排序复杂度为 $O(n \log n)$。即便最终只有少数几个区间只要数据量大最多 $3 \times 10^4$ 次调用、$val$ 取值范围 $0 \le val \le 10^4$排序成本依然可观。可以推断更贴合进阶要求的做法是让区间在addNum时增量维护而不是在getIntervals时全量重建用有序集合如 C 的std::set、Python 中借助sortedcontainers或二分查找维护的列表保存当前的区间起点。addNum(val)时通过二分查找定位val的前驱与后继区间判断是否满足合并条件val落在某个已有区间[start, end]内部start val end无需任何操作val end 1紧邻左区间右侧扩展左区间的右端点val next_start - 1紧邻右区间左侧扩展右区间的左端点两者同时成立将左、右两个区间与val三者合并为一个新区间都不成立val作为孤立点形成新的单点区间[val, val]。getIntervals()直接返回有序集合中已维护的区间列表复杂度为 $O(k)$其中 $k$ 为区间个数。在这种设计下单次addNum的复杂度约为 $O(\log k)$二分定位前驱后继 $O(1)$合并而getIntervals的复杂度与区间数量 $k$ 成正比。当区间数量 $k$ 远小于数据规模 $n$ 时整体表现远优于「每次全量排序」。这也是本题标签中「二分查找、有序集合」的落点所在。四、同类区间题对照AlgoNote 中的区间问题家族AlgoNote 的题解体系中区间相关的题目形成了一条清晰的进阶路线可帮助你横向巩固题目数据形态核心操作参考题解0228. 汇总区间静态有序数组双指针扫描nums[j1] nums[j] 1判连续简单难度双指针 $O(n)$0056. 合并区间静态无序区间列表按左端点排序后线性合并重叠区间经典区间合并模板0352. 将数据流变为多个不相交区间动态数据流集合去重 排序扫描或有序集合增量合并本题困难难度0729. 我的日程安排表 I动态预约请求动态开点线段树/有序集合判重设计类二分查找 有序集合其中与本题设计思路最接近的是 0729. 我的日程安排表 I同样是「设计」标签下的动态区间维护题同样需要在每次插入时快速定位相邻区间。区别在于 0729 关注的是区间是否冲突查询 判重而 0352 关注的是区间如何合并插入 归并两者可以互为对照练习。五、小结回到本题核心要点可以概括为三句话正确性优先addNum用集合 $O(1)$ 去重getIntervals排序后按end 1连续性切分区间思路直白、易于验证适合作为首版实现。性能进阶当区间数量远小于数据量时把「全量重建」改为「增量合并」——用有序集合配合二分查找维护区间可把单次操作成本压到 $O(\log k)$。横向迁移区间判定与合并的思维可以复用到汇总区间、合并区间、日程安排等一整套区间题AlgoNote 的 0300-0399 题解目录 与 LeetCode 题解列表 中收录了大量同类题目供继续练习。掌握「数据结构选型决定复杂度」这一设计题的核心命题你就理解了本题乃至整个「设计 区间」类题目的通用解法框架。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐Apache Beam Java 实战用 FlattenWith 将多个 PCollection 合并为单一数据流Apache Beam Java 实战用 FlattenWith 将多个 PCollection 合并为单一数据流 本文围绕 Apache Beam 官方 J大数据批处理流处理数据工程如何在区块链应用中实现不可变数据存储Objection.js ORM 终极集成指南 如何在区块链应用中实现不可变数据存储Objection.js ORM 终极集成指南 Objection.js 是一个强大的 Node.js ORM对象数据库后端leetcode 题解Number Stream to Intervals数据流区间合并双哈希表与有序字典实现剖析leetcode 题解Number Stream to Intervals数据流区间合并双哈希表与有序字典实现剖析 本篇技术指南以《leetcode 题解文档教程知识库上一篇Elden Ring存档迁移终极指南3步安全转移数百小时游戏进度下一篇免费开源音频频谱分析神器Spek完整使用指南与深度解析创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
阅读完成 · 觉得有帮助？
