在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]
当前回答
简单的代码,让你与多个项目的差异,如果你想要:
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)
其他回答
在字典列表的情况下,当集合解引发时,完整列表理解解工作
TypeError: unhashable type: 'dict'
测试用例
def diff(a, b):
return [aa for aa in a if aa not in b]
d1 = {"a":1, "b":1}
d2 = {"a":2, "b":2}
d3 = {"a":3, "b":3}
>>> diff([d1, d2, d3], [d2, d3])
[{'a': 1, 'b': 1}]
>>> diff([d1, d2, d3], [d1])
[{'a': 2, 'b': 2}, {'a': 3, 'b': 3}]
当查看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]
添加一个答案来处理我们想要严格区别重复的情况,也就是说,在第一个列表中有我们想要保留在结果中的重复。例如,得到,
[1, 1, 1, 2] - [1, 1] --> [1, 2]
我们可以用一个额外的计数器来得到一个优雅的差分函数。
from collections import Counter
def diff(first, second):
secondCntr = Counter(second)
second = set(second)
res = []
for i in first:
if i not in second:
res.append(i)
elif i in secondCntr:
if secondCntr[i] > 0:
secondCntr[i] -= 1
else:
res.append(i)
return res
在这个线程中,我没有看到保留a中的重复的解决方案。当a中的一个元素与B中的一个元素匹配时,这个元素必须在B中删除,这样当相同的元素在a中再次出现时,如果这个元素在B中只出现一次,那么它必须出现在差异中。
def diff(first, second):
l2 = list(second)
l3 = []
for el in first:
if el in l2:
l2.remove(el)
else:
l3 += [el]
return l3
l1 = [1, 2, 1, 3, 4]
l2 = [1, 2, 3, 3]
diff(l1, l2)
>>> [1, 4]
如果你的顺序不重要,两个集合都可以散列,你可以在两个集合之间使用一个对称差分。
这将返回集合A或集合B中出现的值,但不会同时出现。
例如,问题显示了在列表A和列表B上执行的差值的返回值。
如果我们要(将两个列表转换为集合并)执行对称差分,我们将在一次操作中得到两者的合并结果。
A = [1,2,3,4]
B = [2,5]
print(set(A) ^ set(B)
# {1, 3, 4, 5}
加上这个答案,因为我还没有看到现有答案中提供的对称差异