Python 中两个嵌套列表的交集

Question

我对嵌套列表有疑问。我想用 python 语言计算两个嵌套列表的交集的长度。我的列表组成如下：

list1 = [[1,2], [2,3], [3,4]]
list2 = [[1,2], [6,7], [4,5]]
output_list = [[1,2]]

如何计算两个列表的交集？

Answer 1

在 python 中使用集合怎么样？

>>> set1={(1,2),(2,3),(3,4)}
>>> set2={(1,2),(6,7),(4,5)}
>>> set1 & set2
set([(1, 2)])
>>> len(set1 & set2)
1

Answer 2

import json



list1 = [[1,2], [2,3], [3,4]]
list2 = [[1,2], [6,7], [4,5]]

list1_str = map(json.dumps, list1)
list2_str = map(json.dumps, list2)

output_set_str = set(list1_str) & set(list2_str)

output_list = map(json.loads, output_set_str)

print output_list

Answer 3

我认为有两种合理的方法可以解决这个问题。

如果您的顶级列表中没有很多项目，您可以简单地检查其中一个列表中的每个子列表是否存在于另一个列表中：

intersection = [inner_list for inner in list1 if inner_list in list2]

in 运算符将测试相等性，因此可以按预期找到具有相同内容的不同列表对象。然而，这不是很有效，因为列表成员资格测试必须遍历所有子列表。也就是说，它的性能是O(len(list1)*len(list2))。但是，如果您的列表很长，则可能需要比您希望的更多的时间。

一种更渐近有效的替代方法是将内部列表转换为 tuples 并将顶级 lists 转换为 sets。您实际上不需要为此自己编写任何循环，因为 map 和 set 类型的 & 运算符将为您处理所有事情：

intersection_set = set(map(tuple, list1)) & set(map(tuple, list2))

如果您需要结果是 list of lists，您当然可以将 set of tuples 转换回 list 共 list 个：

intersection_list = list(map(list, intersection_set))

Python 中两个嵌套列表的交集

Intersection of two nested lists in Python

intersection

list

python-2.7