0

上周我在一次采访中被问到这个问题,但我没有答案(无论如何都是正确的答案)。例如,您有列表 A,其中包含以下元素 [1,3,5,7,9,10],然后您有列表 B,其中包含以下元素:[3,4,5,6,7],并且您想知道列表 B 中的哪些元素在列表 A 中。我的回答是:

for item in listA:
    for item1 in listB:
        if item1 == item:
            put item1 in some third list

但我知道这很糟糕,因为说 listA 是一百万个元素,而 listB 是十万个,这个解决方案就是垃圾。

在不迭代两个列表的情况下实现此类目标的最佳方法是什么?

4

5 回答 5

6

set(listA) & set(listB)最简单。

于 2012-08-21T04:29:20.723 回答
2

我建议将它们都转换为集合并进行交集:

setA = set(listA)
setB = set(listB)
setA.intersection(setB)

编辑:请注意,这将删除两个列表中的所有重复元素。所以如果我们有listA = [1,1,2,2,3]listB = [1,1,2,3]那么交叉点只会是set([1,2,3])。此外,对于最坏情况的估计,这将与列表理解一样慢 - O(n * m),其中 n 和 m 是列表的相应长度。但是,平均情况要好得多O(n) + O(m) + O(min(m,n)) == O(max(m,n))

于 2012-08-21T04:30:19.637 回答
1

使用列表推导和使用in运算符来测试成员资格:

[i for i in lista if i in listb]

会产生:

[3, 5, 7]

或者,可以使用集合操作并查看两个列表(转换为集合)的交集是什么。

于 2012-08-21T04:30:05.810 回答
1

好吧,我也可以在混合物中加入过滤器

filter(lambda x: x in listb,lista)
于 2012-08-21T04:34:32.190 回答
0

您可以使用集合(首选):

listC = list(set(listA) & set(listB))

或列表理解:

listC = [i for i in listA if i in listB]
于 2012-08-21T04:29:32.023 回答