Python列表操作:给定范围数的列表，返回组合范围的列表
我在一次电话采访中被问到了这个问题：
假设有一个范围列表。例如，[1-6,10-19,5-8]。编写一个函数，返回组合范围的列表，以便向函数输入[1-6,10-19,5-8]返回[1,8],[10,19]。注意，输入列表可能包含任意数量的范围。
我对这个问题的解决办法是：
- 将所有范围列表合并为一个列表：[ 1-6,10-19,5-8 ] -> 1-6，10-19，5-8
- 对列表执行排序: list = -> 1，2，3，4，5，6，6，7，8，10
- 使用list = set(list)消除冗余数字
- 遍历列表并找到范围
我知道这个解决方案肯定是他们想要的(这就是为什么我在面试中失败的原因)，因为时间复杂性是O(nlogn) (排序)，n是范围内不同数字的数目。
你的python专家能给出一个O(n)的解决方案，n作为原始列表中的范围数吗？
回答 3
Stack Overflow用户
发布于 2017-02-17 08:05:22
首先，问题中提到的解决方案不是O(nlgn)，其中n是段数。这里是O(Xlg(X))，X = length of the segment*num of segments，它非常慢。存在一个O(NlgN)解，其中N是段数。
- 按照它们的起点对这些段进行排序。
- 扫描排序列表，并检查当前段是否与前一段重叠。如果是，则在需要时延长前一段。
样本代码：
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]]Stack Overflow用户
发布于 2017-02-17 08:05:11
您可以使用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是范围的数目。
Stack Overflow用户
发布于 2017-02-17 09:02:29
如果范围是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)
https://stackoverflow.com/questions/42292315
复制相似问题
腾讯云开发者
