两个包含重复元素的列表的交集是什么？

Question

>>> a = [1,1,1,2,3,4,4]
>>> b = [1,1,2,3,3,3,4]

[1,1,2,3,4]

请注意，这不是与此相同的问题： Python intersection of two lists keeping duplicates 因为虽然列表a中有三个1，但列表b中只有两个，所以结果应该只有两个。

- Kevin

---

这怎么不是重复的？你理解交集的定义吗？那个问题的问题在于第二个列表的重复项被 set() 移除了。 - OneCricketeer

看起来你需要完成两个步骤。1）创建一个交集列表。2）检查数字是否存在于两个列表中，如果是，则将其附加到交集列表中。 - dot.Py

@OneCricketeer（那个评论已经过时了，但是）你可以看到这两个问题是不同的。这个问题是“正确”的多重集合交集，而另一个问题只是“列表1中存在于列表2中的元素列表”。我不知道是否有好的方法来解释它，但如果你知道，你可以编辑以澄清另一个问题。 - user202729

Answer 1

你可以使用collections.Counter实现此功能。当你求两个列表的交集时，它会为每个元素提供在两个列表中出现次数最少的计数。

from collections import Counter

c = list((Counter(a) & Counter(b)).elements())

输出:

[1, 1, 2, 3, 4]

- miradulo

---

如果我想找到多个列表的交集怎么办？ - Giang Nguyen

要计算>=3个列表之间的交集，请参见Python -Intersection of multiple lists? - Stack Overflow。 - user202729

Answer 2

简单且没有额外的导入，易于调试 :)

缺点：列表 b 的值已更改。如果您不想更改 b，请使用 b 的副本。

c = list()
for x in a:
    if x in b:
        b.remove(x)
        c.append(x)

- mujjiga

---

缺点：它是O(mn)（其中m是a的长度，n是b的长度）。最优解（使用类似于Counter的东西）是O(m + n)。对于OP案例中的小输入，这并不重要，但对于不是那么大的输入（比如每个1000个项目），大约2000个“工作单位”和100万个“工作单位”的差异是相当显着的。 - ShadowRanger

Answer 3

已发布的使用Counter的解决方案很简单，但我认为使用字典的方法也可以，并且速度可能更快 - 即使在未排序的列表上（虽然没有明确提到此要求，但至少另一个解决方案假定这种情况）。

a = [1, 1, 1, 2, 3, 4, 4]
b = [1, 1, 2, 3, 3, 3, 4]
    
def intersect(nums1, nums2):
    match = {}
    for x in nums1:
        if x in match:
            match[x] += 1
        else:
            match[x] = 1
            
    i = []
    for x in nums2:
        if x in match:
            i.append(x)
            match[x] -= 1
            if match[x] == 0:
                del match[x]

    return i

def intersect2(nums1, nums2):
    return list((Counter(nums1) & Counter(nums2)).elements())

timeit intersect(a,b)
100000 loops, best of 3: 3.8 µs per loop

timeit intersect2(a,b)
The slowest run took 4.90 times longer than the fastest. This could mean 
that an intermediate result is being cached.
10000 loops, best of 3: 20.4 µs per loop

我使用大小为1000和10000的随机整数列表进行了测试，结果也更快。

a = [random.randint(0,100) for r in xrange(10000)]
b = [random.randint(0,100) for r in xrange(1000)]

timeit intersect(a,b)
100 loops, best of 3: 2.35 ms per loop

timeit intersect2(a,b)
100 loops, best of 3: 4.2 ms per loop

而对于更大的列表，可能会有更多的共同元素

a = [random.randint(0,10) for r in xrange(10000)]
b = [random.randint(0,10) for r in xrange(1000)]

timeit intersect(a,b)
100 loops, best of 3: 2.07 ms per loop

timeit intersect2(a,b)
100 loops, best of 3: 3.41 ms per loop

- delsauce

---

i 和 c 可能应该是同一个东西吗？i 在初始化后没有被改变，然后作为空列表返回。 - nsheff

嗯，好的。已经修复了，谢谢。 - delsauce

冗长的代码不好。你可以用一行代码完成同样的事情。c = [x for x in a if x in b] - LazerDance

@delsauce：记录一下，慢的Counter问题可能会因为你使用的是Python 2而加剧。在Python 3.2及更高版本中，Counter有一个C加速器用于计算长输入，比您可以在Python中编写的任何循环都要快得多。原始的dict解决方案具有一些微小的优点（流式传输一个输入而不是两个Counter），但它仍然很可能在大多数情况下失败，因为加速器使计数如此快（而交集操作虽然是用Python实现的，但由于每个输入已经被去重到一个计数中，所以最终更便宜）。 - ShadowRanger

你的流媒体解决方案具有完全保留第二个序列中出现顺序的优点（如果翻转计数和流式处理的序列，则会保留来自第一个序列的出现顺序，我个人认为这更可预测）。 - ShadowRanger

Answer 4

这也应该可以工作。

a = [1, 1, 1, 2, 3, 4, 4]
b = [1, 1, 2, 3, 3, 3, 4]
c = []
i, j = 0, 0
while i < len(a) and j < len(b):
    if a[i] == b[j]:
        c.append(a[i])
        i += 1
        j += 1
    elif a[i] > b[j]:
        j += 1
    else:
        i += 1

print(c) # [1, 1, 2, 3, 4]

- Kentaro Wada

---

糟糕的代码。太长了。试试这个：c = [x for x in a if x in b] - LazerDance

Answer 5

这应该也可以工作：

def list_intersect(lisA, lisB):
    """ Finds the intersection of 2 lists including common duplicates"""

    Iset = set(lisA).intersection(set(lisB))
    Ilis = []
    for i in Iset:
        num = min(lisA.count(i), lisB.count(i))
        for j in range(num):
            Ilis.append(i)
    return Ilis

- DrFalcon

Answer 6

这将会做到：

from itertools import chain
list(chain.from_iterable([(val,)*min(a.count(val), b.count(val)) for val in (set(a) & set(b))]))

给出：

[1, 1, 2, 3, 4]

- j4hangir