题目描述
给出一个非负整数的数据流 a1,a2,…an,…a1,a2,…an,…,请将它们动态地维护成一系列不相交的区间。
样例
给定数据流:1, 3, 7, 2, 6, ..., 动态得到的区间是:
[1, 1]
[1, 1], [3, 3]
[1, 1], [3, 3], [7, 7]
[1, 3], [7, 7]
[1, 3], [6, 7]
过程
插入1,m = 0, 右侧直接添加--> [1, 1]
插入3,m = 2, 右侧直接添加-->[1, 1, 3, 3]
插入7,m = 4, 右侧直接添加-->[1, 1, 3, 3, 7, 7]
插入2, m = 2, 判断与右侧重叠,更新-->[1, 1, (2) (3), 3, 7, 7](2将会替换3),继续判断与左侧重叠,更新-->[1, 3, 7, 7]
插入6, m = 2, 判断与右侧重叠,更新-->[1, 3, (6), (7), 7](6将会替换7),继续判断与左侧不重叠,因此结果[1, 3, 6, 7]
对列表奇偶重组,最终结果为[[1, 3], [6, 7]]
Python 代码
class SummaryRanges:
def __init__(self):
# 创建存储所有间隔的列表,例如截止7存储为[1, 3, 6, 7]
self.d = []
def addNum(self, val: int) -> None:
# 二分法查找val应插入的位置,直接采用bisect库函数
m = bisect.bisect(self.d, val)
# 仅当m为偶数时才需要更新,因为间隔每两位为一组,若待插入位置为奇数,则一定位于某一组间隔内
if m % 2 == 0:
#处理右边界
# 若新加入的数与其插入位置右侧的间隔有重叠部分(即差为1),则更新,使插入位置的值val
if m < len(self.d) and self.d[m] - val == 1:
self.d[m] = val
# 若新加入的数的插入位置等于数组长度,即放置在最后,则依次添加间隔对(暂不处理左边界)
else:
self.d.insert(m, val)
self.d.insert(m, val)
# 处理左边界
# 若与左侧间隔有重叠部分,差为1时,删除本身左节点及前向间隔右节点
if m > 0 and self.d[m] - self.d[m - 1] <= 1:#根据现有情况选择是否和左区间合并
self.d.pop(m)
self.d.pop(m - 1)
def getIntervals(self) -> List[List[int]]:
# 间隔列表例如[1, 3, 6, 7], 按奇偶位组合填充列表返回
return [*zip(self.d[:: 2], self.d[1:: 2])] #按奇偶顺序打包输出