给定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是连续的。
我如何构造完成这项工作的函数?
首先,您可以使用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)