Python-python中如何快速获取两个list的交集?

Python-python中如何快速获取两个list的交集?

归属感 发布于 2017-07-17 字数 312 浏览 1186 回复 2

据我所知set有intersection方法,除了把list转换成set之外的方法,即(a = set(a) a.intersection(b)),还有什么方法能过快速计算两个list的交集?

a = [1, 2, 3, 4, 5, 10 ,0]
b = [9, 8, 7, 6, 5, 1];
#类似如下:javascript:void(0)
interlist(a, b) => [1,5]

如果你对这篇文章有疑问,欢迎到本站 社区 发帖提问或使用手Q扫描下方二维码加群参与讨论,获取更多帮助。

扫码加入群聊

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(2

甜柠檬 2017-10-06 2 楼

def interlist(a, b):
'''
worst case: O(max(len(a), len(b))
'''
s = set(b)
return [item for item in a if item in s]

set的in操作复杂度是平均O(1),最坏O(n);这个方法比直接用两个set的intersection更快,set(a) & set(b)的复杂度是平均O(min(len(a), len(b)),最坏O(len(a) * len(b))。
另外list的in操作复杂度平均就为O(n),所以Roland的方法复杂度也比这个方法高,最坏也是O(len(a) * len(b))。
CPython操作时间复杂度

甜柠檬 2017-07-31 1 楼

 M = [item for item in a if item in b]

视你的需求,是不是还要加一句去掉重复元素。