Python中合并列表内连续整数区间子列表的技术问题

你的需求是合并满足后一子列表首元素 = 前一子列表尾元素 + 1的连续区间，原来的多次迭代方案确实不够高效——毕竟每次迭代都要遍历列表，最坏情况下时间复杂度是O(n²)。其实我们只需要一次线性遍历就能完成合并，时间复杂度直接降到O(n)，下面是具体实现思路和代码：

核心思路 #

1. 先处理边界情况：如果输入列表为空，直接返回空列表。
2. 初始化结果列表，把第一个区间先放进去作为初始合并区间。
3. 从第二个区间开始遍历输入列表：
   • 取出结果列表的最后一个区间，对比当前区间的首元素是否等于最后一个区间的尾元素 + 1。
   • 如果满足条件，就更新最后一个区间的尾元素为当前区间的尾元素（完成合并）。
   • 如果不满足，就把当前区间直接添加到结果列表里。

Python 代码实现 #

in_list = [[10, 15], [16,21], [22,25], [26,30], [35,40], [45,50],[51,55]]

def merge_continuous_intervals(intervals):
    if not intervals:
        return []
    
    merged = [intervals[0].copy()]  # 复制第一个区间避免修改原数据
    for current in intervals[1:]:
        last = merged[-1]
        # 检查是否满足合并条件
        if current[0] == last[1] + 1:
            last[1] = current[1]  # 更新尾元素，完成合并
        else:
            merged.append(current.copy())
    return merged

out_list = merge_continuous_intervals(in_list)
print(out_list)  # 输出: [[10, 30], [35, 40], [45, 55]]

代码说明 #

• 用merged[-1]直接获取当前正在合并的最后一个区间，避免多次遍历结果列表。
• 用copy()是为了防止修改原输入列表的区间数据，如果不需要保留原数据，也可以直接用merged = [intervals[0]]。
• 整个过程只遍历输入列表一次，每个元素只处理一次，效率远高于多次迭代的方案。

内容的提问来源于stack exchange，提问作者Kalpit