leetcode 题解：Number Stream to Intervals（数据流区间合并）双哈希表与有序字典实现剖析

leetcode 题解Number Stream to Intervals数据流区间合并双哈希表与有序字典实现剖析【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode本篇技术指南以《leetcode 题解仓库》中的 problems/Number-Stream-to-Intervals.md 为主体完整讲解数据流区间合并数据结构StreamSummary的建模思路、双哈希表合并算法、get排序与SortedDict两种实现策略并结合仓库中 problems/56.merge-intervals.md、problems/1438.longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit.md 等同类题目展开纵深对比。读完本文你将掌握边插入边合并区间类问题的通用解法并能在O(1)与O(logn)两种 add 复杂度方案之间做出正确取舍。题目背景与定义题目来源于 BinarySearch 平台的 820 号题 Number Stream to Intervals对应仓库文档 problems/Number-Stream-to-Intervals.md要求实现一个数据结构StreamSummary支持以下方法StreamSummary()构造一个新的实例。add(int val)把数字val加入实例。int[][] get()返回一个**升序排列、互不相交disjoint**的区间列表区间覆盖所有已经见过的数字。题目给出的约束为n ≤ 10,000其中n是add的调用次数m ≤ 10,000其中m是get的调用次数。示例一methods [constructor, add, add, add, add, get] arguments [[], [1], [3], [2], [9], []] 输出 [None, None, None, None, None, [[1, 3], [9, 9]]]等价于s StreamSummary() s.add(1) s.add(3) s.add(2) s.add(9) s.get() [[1, 3], [9, 9]]解释先加入1再加入3此时两者不相邻加入2后[1,1]、[2,2]、[3,3]三个单点区间连成一片合并为[1,3]最后加入9形成孤立的[9,9]。示例二methods [constructor, add, add, add, add, get] arguments [[], [1], [2], [4], [3], []] 输出 [None, None, None, None, None, [[1, 4]]]等价于s StreamSummary() s.add(1) s.add(2) s.add(4) s.add(3) s.get() [[1, 4]]解释1、2合并为[1,2]4先作为独立区间存在随后加入的3恰好填补了[1,2]与[4,4]之间的空隙三个部分最终合并为[1,4]。前置知识原文档明确列出解决本题需要的前置知识本仓库也有对应主题的深入文章可供延伸阅读哈希表用于以O(1)平均复杂度完成区间端点的查询、插入与删除有序哈希表 / 平衡树用于保证get输出的区间天然有序仓库中 problems/1438.longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit.md 也提到了SortedList/TreeMap/multiset等有序容器在该类问题中的应用二分法理解在有序结构中定位相邻元素的思想参见仓库 thinkings/binary-search-2.md 中关于平衡树与二分查找结合的讨论。思路解析把 add 建模为区间合并题目的核心难点在于数据是以流的形式逐步给出的而不是一次性给出完整数组。因此每次add(val)本质上等价于插入一个左右闭合的单点区间[val, val]并立刻判断它能否与已有的区间合并如果插入的区间能与左边或右边的已有区间合并就将其合并get返回合并之后的全部区间总和。以示例一为例分步观察合并过程s.add(1) # [ [1,1] ] s.add(3) # [ [1,1], [3,3] ] s.add(2) # [ [1,1], [2,2], [3,3] ]可合并为 [ [1,3] ] s.add(9) # [ [1,3], [9,9] ]此时调用get会返回[ [1,3], [9,9] ]。这正是区间合并merge intervals思想在增量式插入场景下的体现。仓库中的 problems/56.merge-intervals.md 处理的是一次性给定全部区间后的静态合并先按左端点排序、再线性扫描而本题的挑战在于每次插入后都要立即保持区间集合的不相交性与正确性因此不能简单套用离线排序做法。双哈希表设计start 与 end 互为索引由于每次add都需要判断新值val是否与左右相邻区间连通原文档给出的做法是同时维护两张哈希表互为索引哈希表startstart[x]表示以x为区间左端点的区间的右端点即它描述区间[ x, start[x] ]哈希表endend[x]表示以x为区间右端点的区间的左端点即它描述区间[ end[x], x ]。start与end存的是同一组区间只是分别以左右端点作为键。这样设计的价值在于判断值val的左边是否存在区间只需检查val - 1 in end说明以val - 1结尾的区间紧邻val判断右边是否存在区间只需检查val 1 in start说明以val 1开头的区间紧邻val。两个方向的邻接查询都能在O(1)内完成。四种合并情况add(val)时共有四种情况需要分别处理仅和左边区间结合val - 1存在于end中即已有区间[a, val-1]。此时[a, val-1]与[val, val]合并为[a, val]。仅和右边区间结合val 1存在于start中即已有区间[val1, b]。此时[val, val]与[val1, b]合并为[val, b]。和左右两边区间都结合val - 1在end中且val 1在start中即同时存在[a, val-1]与[val1, b]。此时[a, val-1] [val, val] [val1, b]三者合并为[a, b]等价于用新值把左右两个区间焊接起来。不和任何区间结合val两侧都没有相邻区间直接新建单点区间[val, val]。原文档特别强调了一个容易被忽略的细节区间合并之后必须把被吞并的旧区间从哈希表中删除。否则残留的键值对会造成区间集合重复或错乱最终影响get的结果。从实现看删除操作针对的是被并入的相邻区间的端点键如情况 3 中的start[val1]与end[val-1]而合并产生的新端点需要写入start与end保持两张表始终描述同一组区间。get 的有序性排序与 SortedDict 两条路线题目要求get返回的区间列表升序排列而普通哈希表的遍历顺序是任意的因此直接遍历start或end无法保证有序。原文档给出两种策略策略一get 时排序add使用普通哈希表时间复杂度为O(1)get时对区间集合排序后再返回时间复杂度为O(m log m)其中m为合并后的区间个数。策略二使用 SortedDict有序哈希表SortedDict内部基于平衡树实现键有序因此add过程中对端点键的定位、插入、删除均为O(logn)get直接按有序键遍历start时间复杂度为O(m)m为合并后的区间个数。两种方法都正确选择依据是add与get的调用频率以及m、n的相对大小若get调用频繁、m较大策略二SortedDict的O(m)遍历优势明显若add调用极其频繁、m相对较小策略一的O(1)插入可能更划算把排序开销摊到get上。原文档给出的结论是当区间合并后数量较少、get调用较多时SortedDict更优反之普通哈希表 排序即可。仓库中 problems/2102.sequentially-ordinal-rank-tracker.md、problems/1438.longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit.md 等题目同样体现了用有序结构换取查询复杂度的取舍思路。完整代码实现原文档给出了基于SortedDict的 Python3 实现依赖sortedcontainers库完整继承如下from sortedcontainers import SortedDict class StreamSummary: def __init__(self): self.start SortedDict() self.end SortedDict() def add(self, val): if val - 1 in self.end and val 1 in self.start: # [a, val-1] [val,val] [val1, b] - [a, b] self.end[self.start[val 1]] self.end[val - 1] self.start[self.end[val - 1]] self.start[val 1] del self.start[val 1] del self.end[val - 1] elif val - 1 in self.end: # [a, val -1] [val, val] - [a, val] self.end[val] self.end[val - 1] self.start[self.end[val]] val del self.end[val - 1] elif val 1 in self.start: # [val,val] [val1, b] - [val, b] self.start[val] self.start[val 1] self.end[self.start[val]] val del self.start[val 1] else: self.start[val] val self.end[val] val def get(self): # iterate start or end get same correct answer ans [] for s, e in self.start.items(): ans.append([s, e]) return ans对代码中关键步骤的逐行解读情况 3左右都结合self.end[val - 1]是左区间[a, val-1]的左端点aself.start[val 1]是右区间[val1, b]的右端点b。合并后新区间为[a, b]因此执行self.end[b] a与self.start[a] b随后删除start[val1]和end[val-1]两个旧键。注意此时val本身从未作为端点写入它恰好被左右两个区间吸收。情况 1仅左结合新区间为[a, val]即self.end[val] a同时更新self.start[a] val删除旧键end[val-1]。情况 2仅右结合新区间为[val, b]即self.start[val] b同时更新self.end[b] val删除旧键start[val1]。情况 4孤立插入start[val] end[val] val表示单点区间[val, val]。get遍历start即可由于SortedDict的键天然升序且start的键恰好是所有区间的左端点按序遍历即可得到升序的不相交区间列表。原文档注释也指出遍历end同样能得到正确答案顺序相反需注意端点拼接方向。若采用策略一普通哈希表 get时排序只需把两个SortedDict()换成dict()并在get中对self.start.items()的结果按左端点排序后返回即可add部分的四种合并逻辑完全一致因为该逻辑只依赖键的成员判断与取值不依赖有序性。复杂度分析令n为数据流长度add调用次数m为合并后的区间个数。采用 SortedDict本文代码时间复杂度add为O(logn)平衡树上的查找、插入、删除get为O(m)有序遍历空间复杂度O(m)start与end各存储m个区间端点常数因子为 2。采用普通哈希表 get 排序时间复杂度add为O(1)get为O(m log m)空间复杂度同样为O(m)。原文档给出的复杂度分析与代码一一对应两个方案的差异集中在插入成本与查询成本的再分配上读者可依据题目约束n、m均不超过10,000灵活选择。同类问题与仓库延伸本题是区间合并家族中偏工程向设计数据结构的变体仓库中与之互相关联的题目可以从多个角度加深理解problems/56.merge-intervals.md离线版本的区间合并先按左端点排序再线性扫描合并是理解合并规则的基础模板problems/1438.longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit.md滑动窗口中用有序容器PythonSortedList/ JavaTreeMap/ Cmultiset维护动态数据与本题用有序结构降低动态维护复杂度的思路一脉相承problems/2172.count-good-triplets-in-an-array.md同样借助SortedList做动态有序统计展示了有序容器在边插入边查询场景下的通用性problems/2817.minimum-absolute-difference-between-elements-with-constraint.md在有序结构中二分定位最近邻元素与本题判断val ± 1是否邻接的邻接查询思想互补本题解法中平衡树保证有序遍历的设计也可结合 thinkings/binary-search-2.md 中关于二分查找与有序结构配合的内容一起复习。小结Number Stream to Intervals是一道典型的动态区间合并 数据结构设计题核心要点可以总结为三条建模把每次add(val)视为插入单点区间[val, val]只与左右相邻区间发生合并从而把问题收敛为四种边界情况双哈希表索引start与end分别以左右端点为键、互为索引使得是否邻接的判断达到O(1)并借助SortedDict或get时排序保证输出有序复杂度取舍O(1)插入 O(m log m)查询与O(logn)插入 O(m)查询两种方案各有适用场景应根据add/get调用频率决定。在仓库目录中本题收录于 problems/Number-Stream-to-Intervals.md并同时登记在 SUMMARY.md 与 README.md 的题解索引中可与上述同类题目配合刷题、对照总结。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考