查找循环列表中缺失的序列

Question

给定2个列表:

target = [0, 1, 2, 3, 4, 5, 6, 7]
given = [1, 2, 5, 6]

缺失的数字为[[0], [3,4], [7]]。然而，list都循环，这意味着列表的末尾与第一个链接，所以它们实际上看起来像这样:

target = [0,1,2,3,4,5,6,7,0,1,2,3,4,5,......]
given = [1,2, 5,6, 1,2, 5,6,......] # I put a space to better tell where numbers missing

这样，缺少数字的期望输出实际上应该是[[7,0], [3,4]]，因为7和0是连续的。

我如何构造完成这项工作的函数?

Answer 1

首先，您可以使用itertools.groupby构建缺失补丁列表，然后在必要时粘合最左和最右的子列表:

import itertools
def missing(target, given):
output = [list(g) for k, g in itertools.groupby(target, key=lambda x: x in given) if not k]
if output and output[0][0] == target[0] and output[-1][-1] == target[-1]:
output[-1] += output.pop(0)
return output
print(missing([0, 1, 2, 3, 4, 5, 6, 7], [1, 2, 5, 6])) # [[3, 4], [7, 0]]
print(missing([0, 1, 2, 3, 4, 5, 6, 7, 8], [1, 2, 5, 6, 8])) # [[0], [3, 4], [7]]

更新:如果您不想导入itertools模块，那么将output = [list(g) ...]行替换为以下内容:

output, temp = [], [] # an empty "temporary bucket"
for x in target:
if x in given:
if temp: # if temp is nonempty
output.append(temp) # put the bucket into output
temp = [] # a new empty bucket
else: # if x is "missing"
temp.append(x) # append x into the bucket
else: # this is called when for loop is over (or target is empty)
if temp: # if the last temporary bucket is nonempty
output.append(temp)