在Python中,计算两个列表之间的差值的最佳方法是什么?
例子
A = [1,2,3,4]
B = [2,5]
A - B = [1,3,4]
B - A = [5]
在Python中,计算两个列表之间的差值的最佳方法是什么?
例子
A = [1,2,3,4]
B = [2,5]
A - B = [1,3,4]
B - A = [5]
当前回答
如果你不关心项目的顺序或重复,请使用set。使用列表推导式:
>>> def diff(first, second):
second = set(second)
return [item for item in first if item not in second]
>>> diff(A, B)
[1, 3, 4]
>>> diff(B, A)
[5]
>>>
其他回答
你可以做一个
list(set(A)-set(B))
and
list(set(B)-set(A))
如果你的顺序不重要,两个集合都可以散列,你可以在两个集合之间使用一个对称差分。
这将返回集合A或集合B中出现的值,但不会同时出现。
例如,问题显示了在列表A和列表B上执行的差值的返回值。
如果我们要(将两个列表转换为集合并)执行对称差分,我们将在一次操作中得到两者的合并结果。
A = [1,2,3,4]
B = [2,5]
print(set(A) ^ set(B)
# {1, 3, 4, 5}
加上这个答案,因为我还没有看到现有答案中提供的对称差异
如果你不关心项目的顺序或重复,请使用set。使用列表推导式:
>>> def diff(first, second):
second = set(second)
return [item for item in first if item not in second]
>>> diff(A, B)
[1, 3, 4]
>>> diff(B, A)
[5]
>>>
当查看in -operator的TimeComplexity时,在最坏的情况下它与O(n)一起工作。即使是集合。
因此,当比较两个数组时,最好情况下的TimeComplexity为O(n),最坏情况下为O(n²)。
另一种(但不幸的是更复杂)解决方案,在最好和最坏的情况下都适用于O(n):
# Compares the difference of list a and b
# uses a callback function to compare items
def diff(a, b, callback):
a_missing_in_b = []
ai = 0
bi = 0
a = sorted(a, callback)
b = sorted(b, callback)
while (ai < len(a)) and (bi < len(b)):
cmp = callback(a[ai], b[bi])
if cmp < 0:
a_missing_in_b.append(a[ai])
ai += 1
elif cmp > 0:
# Item b is missing in a
bi += 1
else:
# a and b intersecting on this item
ai += 1
bi += 1
# if a and b are not of same length, we need to add the remaining items
for ai in xrange(ai, len(a)):
a_missing_in_b.append(a[ai])
return a_missing_in_b
e.g.
>>> a=[1,2,3]
>>> b=[2,4,6]
>>> diff(a, b, cmp)
[1, 3]
您可能希望使用集合而不是列表。