也叫暴力枚举法,也就是把两个list当中的每个元素都取出来进行两两比较,直到找到相同元素。设第一个数组的长度为n,第二个数组的长度为m,则时间复杂度为O(n*m),空间复杂度为O(1)
但是个问题常见的解决方法是哈希表。在Python当中有Dictionary这种数据类型,其实是一个哈希表。运用这种数据类型,可以迅速检索到想要的元素。但这种方法需要存储一组元素,所以时间复杂度为O(n),空间复杂度为O(m)。
以下是程序:
def
find_same_element(l1,
l2):
dist
=
{}
for
i
in
l1:
dist[i]
=
1
for
i
in
l2:
if
dist.get(i)
>
None:
return
i
return
None
以下是检验
l1
=
[1,
2,
'34',
34,
5]
l2
=
[4,
7,
8]
find_same_element(l1,
l2)
应当输出None
l1
=
[1,
2,
'34',
34,
5]
l2
=
[4,
7,
8,5]
find_same_element(l1,
l2)
应当输出5
这个函数只能找到一个共同元素,如果两个list有多个相同元素则只能输出中间的一个。
这个问题常见于面试题,属于最简单的面试题目。需要给面试官说明的是,
第一,哈希表可以快速检索元素,
第二,python有独特的数据类型,
第三,多个共同元素的情况需要面试官告知如何处理,
第四,注意没有共同元素的时候的输出(程序中为None但面试官希望你能提出这个问题)
可以对第二个list的元素进行遍历,检查是否出现在第二个list当中,如果使用表理解,可以使用一行代码完成任务。list1 = [1,2,3,4,5]
list2 = [4,5,6,7,8]
print [l for l in list1 if l in list2]
# [4,5]
如果每一个列表中均没有重复的元素,那么还有另外一种更好的办法。首先把两个list转换成set,然后对两个set取交集,即可得到两个list的重复元素。
set1 = set(list1)
set2 = set(list2)
print set1 &set 2
# {4,5}