两个列表的交集,包括重复？

Question

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

[1,1,2,3,4]

请注意这不是同一个问题: 两个列表的Python交集保持重复 因为即使列表a中有三个1,列表b中只有两个,因此结果应该只有两个.

Answer 1

您可以使用collections.Counter此选项,当您选择交叉点时,它将为每个元素的任一列表中提供最低计数.

from collections import Counter

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

产出:

[1, 1, 2, 3, 4]

Answer 2

简单，无需额外导入，易于调试 :)

缺点：list b 的值发生了变化。如果您不想更改 b，请处理 b 的副本。

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

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 a:
        if x in match:
            match[x] += 1
        else:
            match[x] = 1

    i = []
    for x in b:
        if x in match:
            c.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