主页 / 问题 / 1599656
Accepted
s0m
Asked:2024-11-13 16:30:18 +0000 UTC2024-11-13 16:30:18 +0000 UTC

需要合并范围[关闭]

  • 772

我有一个列表列表：

[[1, 2], [2, 3], [5, 8], [10, 11], [4, 6]]

有必要比较元素，并在范围相交时进行并集，以便选择最大范围。

输出应该是：

[[1, 3], [4, 8], [10, 11]]
python

3 个回答

  1. Best Answer
    def gen(lst):
    if len(lst) < 1:
        return
    if len(lst) < 2:
        yield lst[0]

    lst = sorted(lst, key=lambda x: (x[0], x[1]))  # сортируете список
    print(lst)
    x = lst[0][0]  # начальная точка 
    y = lst[0][1]  # конечная точка
    for i in lst[1:]:
        if i[0] <= y:  # если в следующем списке начало равно или меньше конца предыдущего
            y = i[1]   # заменяем конец
        else:
            yield [x, y]  # отдаем интервал
            x = i[0]      # переопределяем начало  и конец   
            y = i[1]

    yield [x,y]
    return

lst = [[1, 2], [2, 3], [5, 8], [10, 11], [4, 6]]

res = []
for i in gen(lst):
    res.append(i)
print(res)  #  [[1, 3], [4, 8], [10, 11]]
    • 1
    • 将第一个列表元素添加到新列表中
    • 对于剩余的元素，遍历新列表并查找该范围是否与现有的不相交
    • 如果相交，则将其与现有的合并
    • 如果不相交，则将其添加到新列表中
    • 如果在列表处理期间存在连接，那么您将需要使用新列表再次运行此算法，因为可能会出现其他连接
    • 当连接结束时，算法结束

    O(n^2) 不好（甚至 O(n^3)），需要优化。也许按第一个元素和第二个元素对列表进行排序会有所帮助，再加上“双指针方法”来绕过它们；这里我们需要进一步思考。

    • 0

  3. 将范围的所有末端添加到对列表中[значение, признак +1/-1 для начала или конца соответственно]

    对列表进行排序

    启动活动范围计数器

    迭代列表，将该对的第二个字段添加到计数器中。

    如果计数器从0变成1，那么新的组合范围已经开始，记住开始

    如果计数器从1变成0，那么新的组合范围已经结束，将其添加到结果中

    排序导致的复杂度为 O(nlogn)

    默认排序会导致如果值相同则结束点先于开始点处理，因此 [0,1] 和 [1,2] 不会合并。如果需要，则可以将符号反转（-1/+1），并在通过时从计数器中减去它。

    • 0

相关问题