找出两个Python列表的“重叠”部分

Question

给定两个列表：

a = [3,4,5,5,5,6]
b = [1,3,4,4,5,5,6,7]

我想找出它们的“重叠部分”：

c = [3,4,5,5,6]

我还想提取出“剩余部分”，也就是a和b中不在c里的部分。

a_remainder = [5,]
b_remainder = [1,4,7,]

注意：

a里面有三个5，b里面有两个。

b里面有两个4，而a里面有一个。

最终的列表c应该有两个5（受限于列表b）和一个4（受限于列表a）。

这样我就得到了我想要的结果，但我总觉得还有更好的方法。

import copy

a = [3,4,5,5,5,6]
b = [1,3,4,4,5,5,6,7]

c = []
for elem in copy.deepcopy(a):
    if elem in b:
        a.pop(a.index(elem))
        c.append(b.pop(b.index(elem)))

# now a and b both contain the "remainders" and c contains the "overlap"

另外，能不能给我一个比“重叠”和“剩余”更准确的名称，来描述我想要的内容？

Answer 1

在集合的语言中，重叠的部分叫做“交集”，而剩下的部分叫做“集合差”。如果你有不同的项目，你就不需要自己去做这些操作。如果你感兴趣，可以看看这个链接：http://docs.python.org/library/sets.html。

因为我们现在处理的不是不同的元素，所以你的方法是合理的。如果你想让这个过程更快，可以为每个列表创建一个字典，把数字和每个数组中有多少个元素对应起来（比如，在a中，3->1，4->1，5->2，等等）。然后你可以遍历这个字典，检查那个字母是否存在，减少它的数量，并把它加到新的列表中。

这段代码还没测试过，但大致就是这个思路。

def add_or_update(map,value):
    if value in map:
        map[value]+=1
    else
        map[value]=1

b_dict = dict()
for b_elem in b:
    add_or_update(b_dict,b_elem)

intersect = []; diff = [];

for a_elem in a:
    if a_elem in b_dict and b_dict[a_elem]>0:
        intersect.add(a_elem);

for k,v in diff:
    for i in range(v):
        diff.add(k);

Answer 2

使用 Python 的集合

intersection = set(a) & set(b)
a_remainder = set(a) - set(b)
b_remainder = set(b) - set(a)

Answer 3

在Python 2.7中，有一个叫做collection.Counter的工具，可以用来实现多重集合（multisets），它能完美满足你的需求。

a = [3,4,5,5,5,6]
b = [1,3,4,4,5,5,6,7]

a_multiset = collections.Counter(a)
b_multiset = collections.Counter(b)

overlap = list((a_multiset & b_multiset).elements())
a_remainder = list((a_multiset - b_multiset).elements())
b_remainder = list((b_multiset - a_multiset).elements())

print overlap, a_remainder, b_remainder