在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]
当前回答
当查看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]
其他回答
最简单的方法,
使用设置().difference(设置())
list_a = [1,2,3]
list_b = [2,3]
print set(list_a).difference(set(list_b))
答案设置([1])
当查看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]
您可能希望使用集合而不是列表。
简单的代码,让你与多个项目的差异,如果你想要:
a=[1,2,3,3,4]
b=[2,4]
tmp = copy.deepcopy(a)
for k in b:
if k in tmp:
tmp.remove(k)
print(tmp)
如果顺序无关紧要,你可以简单地计算集合差值:
>>> set([1,2,3,4]) - set([2,5])
set([1, 4, 3])
>>> set([2,5]) - set([1,2,3,4])
set([5])