在具有重复元素的两个列表之间查找共同项 python 3

Question

很多 posts or How to find list intersection? 旨在找到两个列表之间的 unique 个项目：

这是我的两个列表：

list1=[1, 2, 2, 3, 3, 4, 4, 5, 10, 12] 
list2=[1, 1, 2, 2, 3, 4, 4, 5, 8, 18]

我的答案是找共同项，可以重复的项。例如，一个 1 出现在这两个列表中，因此 res 应该包含一个 1。两个列表中出现两个2，res应该包含两个2，等等

res = [1 ,2, 2, 3, 4, 4, 5]

顺序无所谓，我的尝试是使用：

res = [x for x in list2 if x in list1]
# res = [1, 1, 2, 2, 3, 4, 4, 5] by above code

但是，这是不正确的，怎么办？

Answer 1

我能想到的唯一方法是边走边从 list2 中删除项目：

list1 = [1, 2, 2, 3, 3, 4, 4, 5, 10, 12]
list2 = [1, 1, 2, 2, 3, 4, 4, 5, 8, 18]

res = []

for x in list1:
    if x in list2:
        res.append(x)
        list2.remove(x)

print(res)

我很好奇是否有更好的答案。

Answer 2

传统方法行不通，因为在第二个 for 循环中，它再次遍历整个列表并再次找到相同的元素，即使它在之前被考虑过。

您需要一种机制来消除已经考虑过的元素。
例如：当您在 list2 上迭代 list1 并遇到 3。在第一次迭代中，您会在 list2 中找到它。但是，当您继续前进并考虑下一个元素时，它又是 3，您会再次发现它是 list2 中的公共元素，因为您是从头开始迭代 list2。

解决方法如下：

一旦我们在 list2 中遇到重复元素，我们就会将其从 list2 中删除。


a = [1, 2, 2, 3, 3, 4, 4, 5, 10, 12]
b = [1, 1, 2, 2, 3, 4, 4, 5, 8, 18]

def remove_duplicates(x,y):
    res = []
    for i in x:
        for j in y:
            if j == i:
                res.append(j)
                y.remove(j)
    return res
    
print(remove_duplicates(a,b))

另一种使用 函数式编程 的方法是使用 map() 将 list2 转换为数据结构，以便它为每个元素保存两个值列表：[(1, True),(2, True), ...]

迭代时，只访问设置为True
的元素并且，每当我们找到一个公共元素时，我们就将该元素的 True 设置为 False

Answer 3

基于计数器的替代解决方案：

import collections

def intersection(A,B):
    c_a=collections.Counter(A)
    c_b=collections.Counter(B)
    duplicates=[]
    for c in c_a:
        duplicates+=[c]*min(c_a[c],c_b[c])
    return duplicates


list1=[1, 2, 2, 3, 3, 4, 4, 5, 10, 12] 
list2=[1, 1, 2, 2, 3, 4, 4, 5, 8, 18]
print(intersection(list1,list2))

在具有重复元素的两个列表之间查找共同项 python 3

Find common items between two lists with repeated elements python 3

list

repeat

python-3.x

解决方法如下：