Python 3 - 查找丢失的元组范围

Question

假设我有一些从 0 开始到 48 结束的 int 范围。

如何从给定的数组中找到丢失的包含序列？

Given: [(10, 12), (12, 37)] 
Output: [(0,10),(37,48)]


Given: [(9, 15)] 
Output: [(0,9),(15,48)]


Given: [(0, 15), (15, 17), (17, 19), (21,25)] 
Output: [(19,21),(25,48)]


Given: [(23, 35),(40,47)] 
Output: [(0,23),(35,40),(47,48)]

Answer 1

我们只需要遍历已排序 的元组范围，找到 i 之间缺失的项在列表中的位置，以及 i+1位置。

第一个和最后一个元组是边缘情况，需要单独考虑，以及空输入情况。这是一个可能的算法:

def find_missing_ranges(tuples, start=0, end=48):
    # edge case: empty input
    if not tuples:
        return [(start, end)]
    ans = []
    # sort the input
    lst = sorted(tuples)
    # edge case: handle start of range
    if lst[0][0] != 0:
        ans.append((start, lst[0][0]))
    for i in range(len(lst) - 1):
        # normal case, find holes between tuples i and i+1
        if lst[i][1] != lst[i + 1][0]:
            ans.append((lst[i][1], lst[i + 1][0]))
    # edge case: handle end of range
    if lst[-1][1] != end:
        ans.append((lst[-1][1], end))
    return ans

它与示例输入一起按预期工作:

find_missing_ranges([])
=> [(0, 48)]

find_missing_ranges([(0, 48)])
=> []

find_missing_ranges([(10, 12), (12, 37)])
=> [(0, 10), (37, 48)]

find_missing_ranges([(9, 15)])
=> [(0, 9), (15, 48)]

find_missing_ranges([(0, 15), (15, 17), (17, 19), (21, 25)])
=> [(19, 21), (25, 48)]

find_missing_ranges([(23, 35), (40, 47)])
=> [(0, 23), (35, 40), (47, 48)]