首页 > 代码库 > 尾递归做区间合并插入示例

尾递归做区间合并插入示例

有一区间列表ranges [[0, 2], [4, 6], [8, 10], [12, 14]],按序排列好了的,没有交集。现在有一新范围range_new [4, 9],进行合并。

采用递归思想,可以用range_new依次和ranges中的范围比较

如果range_new是子集,直接返回

如果range_new小于当前范围,左边直接插入

如果range_new大于当前范围,递归ranges右边的范围比较

如果range_new存在交集,求并集,删除当前范围,如果最大值变化,用并集递归ranges右边的范围比较;如果最大值没有变化,直接替换到当前范围位置

 

求并集代码,返回状态码, -1是左边插入, 1表示继续递归遍历右边,2表示需要更新当前范围,并与后面的范围进行比较,0表示仅替换当前范围

# 求并集
def xor(range_old, range_new):
# 【插入左边】新范围最大值小于老范围最小值
if range_new[1] < range_old[0]:
return -1, range_new
# 【插入右边】新的最小值大于老范围的最大值,在右边
elif range_new[0] > range_old[1]:
return 1, range_new
# 存在交集
else:
# 最小值更新
if range_new[0] < range_old[0]:
# 【最小值更新】不用遍历列表
if range_new[1] < range_old[1]:
return 0, [range_new[0], range_old[1]]
# 【最小值最大值更新】,需要判断最大值与后面的范围是否有交集
else:
return 2, range_new
# 最小值不用更新
else:
# 【不更新】最大值也不用更新
if range_new[1] <= range_old[1]:
return 0, None
# 【最大值更新】,需要判断最大值与后面的范围是否有交集
else:
return 2, [range_old[0], range_new[1]]
 
# 尾递归
def tail_rescuvie(ranges, range_new, start=0):
print(‘Start:‘, range_new)
# ranges末尾插入
if start >= len(ranges):
ranges.append(range_new)
return

result, range_or = xor(ranges[start], range_new)
# 左边插入
if result == -1:
ranges.insert(start, range_new)
# 继续遍历右边
elif result == 1:
tail_rescuvie(ranges, range_new, start+1)
# 替换
elif result == 0:
if range_or is not None:
ranges[start] = range_or
return
# 删除范围,用新范围继续向后递归
elif result == 2:
del ranges[start]
print(‘Rescuvie:‘, start, range_new, range_or)
return tail_rescuvie(ranges, range_or, start)
else:
pass


if __name__ == ‘__main__‘:
# ranges = [] # [[1, 2], [8, 9], [100, 200], [205, 300]]
import time
ranges = [[x, x+2] for x in range(0, 15, 4)]
print ‘ranges:‘, ranges
start = time.time()
tail_rescuvie(ranges, [4, 9])
print ‘ranges:‘, ranges

print ‘cost:‘, time.time() – start
执行结果如下:

ranges: [[0, 2], [4, 6], [8, 10], [12, 14]]
(‘Start:‘, [4, 9])     与[0,2]比较
(‘Start:‘, [4, 9])     与[4,6]比较合并
(‘Rescuvie:‘, 1, [4, 9], [4, 9])
(‘Start:‘, [4, 9])   与[8,10]比较合并
ranges: [[0, 2], [4, 10], [12, 14]]
cost: 0.00200009346008

尾递归做区间合并插入示例