LeetCode 题解工作台
将数据流变为多个不相交区间
给你一个由非负整数组成的数据流输入 a 1 , a 2 , ..., a n ，请你将目前为止看到的数字汇总为一组不相交的区间列表。 实现 SummaryRanges 类： SummaryRanges() 初始化一个空的数据流对象。 void addNum(int value) 将整数 value …
3
题型
3
代码语言
3
相关题
当前训练重点
困难 · 二分·搜索·答案·空间
答案摘要
class SummaryRanges: def __init__(self):
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·搜索·答案·空间 题型思路
题目描述
给你一个由非负整数组成的数据流输入 a1, a2, ..., an，请你将目前为止看到的数字汇总为一组不相交的区间列表。
实现 SummaryRanges 类：
SummaryRanges()初始化一个空的数据流对象。void addNum(int value)将整数value添加到数据流中。int[][] getIntervals()返回当前数据流中的整数汇总为一组不相交的区间列表[starti, endi]。答案应按starti升序排序。
示例 1：
输入 ["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 <= value <= 104- 最多会调用
addNum和getIntervals方法3 * 104次。 - 最多会调用
getIntervals方法102次。
进阶：如果存在大量合并，并且与数据流的大小相比，不相交区间的数量很小，该怎么办?
解题思路
方法一
class SummaryRanges:
def __init__(self):
self.mp = SortedDict()
def addNum(self, val: int) -> None:
n = len(self.mp)
ridx = self.mp.bisect_right(val)
lidx = n if ridx == 0 else ridx - 1
keys = self.mp.keys()
values = self.mp.values()
if (
lidx != n
and ridx != n
and values[lidx][1] + 1 == val
and values[ridx][0] - 1 == val
):
self.mp[keys[lidx]][1] = self.mp[keys[ridx]][1]
self.mp.pop(keys[ridx])
elif lidx != n and val <= values[lidx][1] + 1:
self.mp[keys[lidx]][1] = max(val, self.mp[keys[lidx]][1])
elif ridx != n and val >= values[ridx][0] - 1:
self.mp[keys[ridx]][0] = min(val, self.mp[keys[ridx]][0])
else:
self.mp[val] = [val, val]
def getIntervals(self) -> List[List[int]]:
return list(self.mp.values())
# # Your SummaryRanges object will be instantiated and called as such:
# # obj = SummaryRanges()
# # obj.addNum(val)
# # param_2 = obj.getIntervals()
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(log(N)) |
| 空间 | O(N) |
面试官常问的追问
外企场景- question_mark
Assess whether the candidate understands how binary search can optimize interval management.
- question_mark
Look for an explanation of how to balance interval merging with insertion efficiency.
- question_mark
Evaluate the candidate's approach to managing sorted data and maintaining efficient performance.
常见陷阱
外企场景- error
Failing to account for merging intervals properly when adding numbers.
- error
Not using binary search effectively, leading to slower insertion times.
- error
Misunderstanding the space complexity and overcomplicating the storage of intervals.
进阶变体
外企场景- arrow_right_alt
Handling negative numbers in the data stream.
- arrow_right_alt
Optimizing for concurrent access or thread safety in a multithreaded environment.
- arrow_right_alt
Modifying the problem to return intervals in a specific order or format.