将两个列表相交，并计算每个元素重叠的次数

Question

我用以下代码将两个列表相交：

def interlist(lst1,lst2): 
    lst3 = list(filter(lambda x: x in lst1, lst2))

    return lst3

问题是，我想计算lst1和lst2之间的每个交集。结果应该是一个字典将元素映射到两个列表中元素重叠的次数。你知道吗

Answer 1

下面是一个使用collections.Counter和设置交集的简单解决方案。其思想是首先分别计算每个列表中每个元素的出现次数；然后，对于每个元素，重叠的数量是两个计数的min。它将一个列表中的每个匹配项与另一个列表中的单个匹配项进行匹配，因此min给出了可以进行匹配的数量。我们只需要计算两个列表中出现的元素，所以我们取两个键集的交集。你知道吗

如果您想计算所有匹配对（即lst1中的每个匹配项都与lst2中的每个匹配项匹配），请将min(c1[k], c2[k])替换为c1[k] * c2[k]。这统计了从lst1和lst2中选择一个匹配项的方法数。你知道吗

from collections import Counter

def count_intersections(lst1, lst2):
    c1 = Counter(lst1)
    c2 = Counter(lst2)
    return { k: min(c1[k], c2[k]) for k in c1.keys() & c2.keys() }

示例：

>>> lst1 = ['a', 'a', 'a', 'b', 'b', 'c', 'e']
>>> lst2 = ['a', 'b', 'b', 'b', 'd', 'e']
>>> count_intersections(lst1, lst2)
{'b': 2, 'a': 1, 'e': 1}

此解决方案在O（m+n）时间内运行，最多使用O（m+n）辅助空间，其中m和n是两个列表的大小。你知道吗