Python列表操纵:给定范围列表，返回组合范围的列表

Question

我在电话采访中得到了这个问题：

假设有范围列表。例如，[[1-6]，[10-19]，[5-8]]。 编写一个返回组合范围列表的函数 这样的输入[[1-6]，[10-19]，[5-8]]返回 [[[1,8]，[10,19]]（仅开始和终点）。注意，输入列表 可能包含任意数量的 范围。

我对此问题的解决方案是：

1. 将所有范围列表组合到一个列表中：[[1-6]，[10-19]，[5-8]] -> [1-6,10-19,5-8]

2. 在列表中执行排序：list =排序（列表） -> [1,2,3,4,5,5,6,6,6,7,8,10 ...]

3. 使用list = set（list）以摆脱冗余数字

4. 迭代列表并找到范围

我知道这个解决方案绝对是他们正在寻找的东西（这就是为什么我非常失败的面试失败），因为时间复杂性是o（nlogn）（排序），n是该范围内不同数字的数量。

您可以给Python专家提供O（n）解决方案，n是原始列表中的范围吗？

Answer 1

首先，问题中提到的解决方案不是o（nlgn），其中n是段数。这是O（XLG（X）），其中X = length of the segment*num of segments非常慢。存在o（nlgn）溶液，其中n是段数。

1. 按其起点分类段。
2. 浏览排序列表，并检查当前段是否与上一个段重叠。如果是，请在需要时扩展上一段。

示例代码：

inp = [[1,6], [10,19], [5,8]]
inp = sorted(inp)
segments = []
for i in inp:
    if segments:
        if segments[-1][1] >= i[0]:
            segments[-1][1] = max(segments[-1][1], i[1])
            continue
    segments.append(i)
print segments # [[1, 8], [10, 19]]

Answer 2

您可以使用heapq从范围内创建堆。然后，从堆和与堆顶部重叠的流行范围，用合并范围代替顶部。如果没有重叠或没有更多的范围将其附加到结果：

import heapq
def merge(ranges):
    heapq.heapify(ranges)
    res = []
    while ranges:
        start, end = heapq.heappop(ranges)
        if ranges and ranges[0][0] <= end:
            heapq.heapreplace(ranges, [start, max(end, ranges[0][1])])
        else:
            res.append((start, end))
    return res
ranges = [[1,6],[10,19],[5,8]]
print(merge(ranges))

输出：

[(1, 8), (10, 19)]

上面的 o（n log n）时间复杂性，其中 n 是范围的数量。

Answer 3

如果范围为[x，y]，而max_x，y可能在数百万美元之内，您可以做到这一点

这个想法是，我使用哈希的技术将它们放在分类顺序中，利用较低的max_y。

然后我们迭代并保持当前的"良好"范围是变量MN和MX。

如果新范围完全超出了"良好"范围，我们将附加良好的范围并将新范围作为良好范围。否则我们会相应地更改良好范围。

max_y = 1000000
range_sort = [None]*max_y
ranges =  [[1,6],[10,19],[5,8]]
for r in ranges:
    if range_sort[r[0]] is not None and range_sort[r[0]]>=r[1]:
         continue   ## handling the case [1,5] [1,8]
    range_sort[r[0]] = r[1]   # in the list lower value is stored as index, higher as value
mx = -1
mn = 1000000000
ans = []
for x,y in enumerate(range_sort): # The values are correct as explained in comment above
    if y is None:
        continue   #To remove the null values
    if x<mn:
        mn = x    # This will change the lower value of current range
    if x>mx and mx>0: # If lower val x higher than current upper mx
        ans.append([mn,mx])  # append current lower (mn) and upper(mx)
        mn = x   
        mx = y   # change the current upper and lower to the new one 
    if y>mx:
        mx = y   # This will change upper value of current range
ans.append([mn,mx]) # This has to be outside as last range won't get appended
print ans

输出：[[1,8]，[10,19]

时间复杂性 o（max_y）