查找范围值列表中的空白

Question

我在其他编程语言（ruby、C++、JS 等）中发现了许多类似的问题，但在 Python 中却没有。因为Python有例如itertools我想知道我们是否可以在Python中更优雅地做同样的事情。

假设我们有一个“完整范围”，[1,100]然后是“完整范围”内/匹配“完整范围”的范围子集：

• [10,50]

• [90,100]

[1,9]在本例中，我们如何提取未覆盖的位置[51,89]？

这是一个玩具示例，在我的真实数据集中，范围高达数千。

Answer 1

这是一个使用以下方法的巧妙解决方案itertools.chain：我假设输入范围不重叠。如果确实如此，则需要首先使用范围并集算法对其进行简化。from itertools import chaindef range_gaps(a, b, ranges):    ranges = sorted(ranges)    flat = chain((a-1,), chain.from_iterable(ranges), (b+1,))    return [[x+1, y-1] for x, y in zip(flat, flat) if x+1 < y]举range_gaps(1, 100, [[10, 50], [90, 100]])个例子：首先对范围进行排序，以防它们尚未按顺序排列。如果保证它们是有序的，则不需要这一步。然后flat是一个迭代器，它将给出序列0, 10, 50, 90, 100, 101。由于flat是惰性评估的，并通过迭代消耗它，zip(flat, flat)因此给出了像 之类的对序列(0, 10), (50, 90), (100, 101)。所需的范围就像(1, 9), (51, 89)和 的情况一样(100, 101)，应该给出一个空范围，因此它被丢弃。

Answer 2

假设列表仅包含整数，并且子范围按递增顺序且不重叠，您可以使用以下代码。此代码将一一获取所有子范围，并将与原始完整范围及其之前的子范围进行比较，以找到丢失的范围。[start,end]=[1,100]chunks=[[25,31],[7,15],[74,83]]print([r for r in [[start,chunks[0][0]-1] if start!=chunks[0][0] else []] + [[chunks[i-1][1]+1, chunks[i][0]-1] for i in range(1,len(chunks))]+[[chunks[-1][1]+1,end] if end!=chunks[-1][1] else []] if r])输入[1,100][[7,15],[25,31],[74,83]]输出[[1, 6], [16, 24], [32, 73], [84, 100]]如果不能保证子范围的递增顺序。您可以包含以下行来对块进行排序。chunks.sort(key=lambda x: x[0])

Answer 3

这是一个通用的解决方案：def gap(N, ranges):&nbsp; &nbsp; ranges=[(min1, max1), (min2, (max2), ......, (minn, maxn)]&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; original=set(range(N))&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; &nbsp; for i in ranges:&nbsp; &nbsp; &nbsp; &nbsp; original=original-set(range(i[0], i[1]))&nbsp; &nbsp; return original