修改范围之间的一组值

Question

我有一个结构为 [(2, 4), (6, 7)] 的索引范围列表。我还有一个包含 10 个元素的数组，所有元素的值为 False：

[False, False, False, False, False, False, False, False, False, False]

我想做的是修改这些范围之间的值并使它们为真。所以最终名单将是：

[False, True, True, True, False, True, True, False, False, False]

注意：列表的索引不是从零开始的。

我正在考虑基于两个 for 的解决方案，但它具有 N^2 复杂性：

for i in range(len(list_ranges)):
    for j in range(len(my_list)):
        if (j >= list_ranges[i][0] or j <= list_ranges[i][1]):
            my_list[j] = True

如何提高算法的复杂度？

Answer 1

您只能更新相应的列表片段（就地修改列表，您已经在 my_list 中这样做了）。如果设置的项目数相等，则列表集切片是 O(K) operation。

>>> list_ranges = [(2, 4), (6, 7)]
>>> my_list = [False, False, False, False, False, False, False, False, False, False]
>>> list_ranges = [(2, 4), (6, 7)]
>>> for start, end in list_ranges:
...     my_list[start-1:end] = [True] * (end - start + 1)
...
>>> my_list
[False, True, True, True, False, True, True, False, False, False]

请注意，这将在内存中启动中间列表，然后将它们分配给原始列表中的相应索引。

其次，如果范围列表比较小，那么我们可以检查索引是否位于给定的任何范围内。

>>> def solve(indices, my_list):
...     return [any(start <= index <= end for start, end in indices) for index, item in enumerate(my_list, start=1)]
...
>>> my_list = [False, False, False, False, False, False, False, False, False, False]
>>> solve(ranges, my_list)
[False, True, True, True, False, True, True, False, False, False]

修改范围之间的一组值

Modify group of values between a range

python

performance

list

time-complexity