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 回答