如何优化修改数组指定索引区间内元素值的算法时间复杂度

原有代码问题 #

首先你现有实现存在两个核心问题：

1. 逻辑错误：判断条件误用or运算符，只要j >= 区间左或j <= 区间右任意一个成立就赋值为True，会导致所有数组元素都被改为True，不符合需求，正确的判断逻辑应该用and运算符。
2. 效率问题：两层嵌套循环的时间复杂度为O(M*N)（M为区间数量，N为数组长度），存在大量无意义的遍历操作。

优化方案 #

方案1：切片直接赋值（适合区间数量少、重叠少的场景） #

利用Python列表的切片赋值特性，直接对区间覆盖的位置批量赋值，时间复杂度为O(M + K)，K为所有区间覆盖的总元素数，远低于原有实现的复杂度。
注意：题目明确数组索引从1开始计数，需要转换为Python默认的0基索引适配

# list_ranges = [(2, 4), (6, 7)]
# my_list = [False] * 10
for left, right in list_ranges:
    start = left - 1  # 1基左边界转0基
    end = right       # 适配Python切片左闭右开特性
    my_list[start:end] = [True] * (end - start)

方案2：差分数组法（适合区间数量多、重叠多的场景） #

如果区间数量很大、重叠度高，用差分数组可以实现固定O(M + N)的时间复杂度，无需关心区间重叠情况：

n = len(my_list)
# 差分数组多开一位避免越界
diff = [0] * (n + 1)
for left, right in list_ranges:
    start = left - 1
    end = right
    diff[start] += 1
    diff[end] -= 1

# 前缀和计算，大于0的位置属于至少一个区间
prefix = 0
for i in range(n):
    prefix += diff[i]
    if prefix > 0:
        my_list[i] = True

两种方案都可以直接得到你需要的结果：[False, True, True, True, False, True, True, False, False, False]

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