python - 有效地查找两个列表之间的元素差异

Question

鉴于列表 a和 b ，其中 a与 b 相比多了一个元素，我试图找到唯一存在于 a 中的额外元素以一种有效的方式。虽然这可以使用 set(a) ^ set(b) 轻松完成，问题是a和 b可以包含多个应独立处理的同名元素。
例如:

a = ['Orange', 'Orange', 'Apple', 'Tomato', 'Orange', 'Watermelon']
b = ['Watermelon', 'Orange', 'Tomato', 'Orange', 'Apple']

结果应该返回额外的 'Orange'列表中的内容 a .我的代码是:

def ListDiff(a, b):
    for element in a:
        if element in b:
            b.remove(element)
        else:
            solution = element
    return solution

但显然使用 remove()永远不可能是最有效和最优化的方式，尤其是如果 a和 b很大。有没有一种有效的方法来定位额外的元素？

Answer 1

您可以在 O(n log(n)) 中完成时间使用排序。排序后，可以进行线性遍历，找到第一个差异。重复元素使二进制搜索复杂化，否则这是可能的。

def ldiff(a, b):
    a.sort()
    b.sort()
    for i, j in zip(a, b):
        if i != j:
            break
    else:
        i, j = a[-1], b[-1]
    return i if len(a) > len(b) else j 

如果您反对由 sort 执行的就地修改方法，使用 sorted函数代替。