在使用for循环python的两个列表中查找公共项--降低时间复杂度
在使用for循环python的两个列表中查找公共项--降低时间复杂度
提问于 2021-09-19 20:54:43
在一次采访中，我被要求在Python中的两个列表之间找到常见的条目。我提供了三种解决方案:使用set.intersection、列表理解和for循环。下面是我执行的for循环：
def common_elements(list1, list2):
result = []
for element in list1:
if element in list2:
result.append(element)
return result在我做完for循环之后，面试官问我，是否有任何方法可以通过不必查看列表中的每一项来降低时间复杂性。他还暗示我可以先对名单进行排序。我无法回答这个问题，我仍在努力解决这个问题。我如何处理这个问题？
回答 3
Stack Overflow用户
回答已采纳
发布于 2021-09-20 02:31:37
您可以结合一个for-循环和一个迭代器，并行遍历排序列表，并在此过程中生成匹配。
def common(L1,L2):
iter2 = iter(sorted(L2)) # iterator on sorted L2 values
Done = object() # flag to identify end of iteration
v2 = next(iter2,Done) # get first (lowest) element of L2
for v1 in sorted(L1):
while v2 is not Done and v2<v1:
v2 = next(iter2,Done) # advance in sorted L2 to reach or surpass v1
if v1 == v2:
yield v1 # return matches
v2 = next(iter2,Done) # advance (only match items once each)
if v2 is Done: break # stop if L2 values exausted
for c in common([3,7,4,2,4,3,1],[4,5,2,2,4,3]):
print(c)
2
3
4
4这将具有O(NlogN + MlogM)的时间复杂度，而不是O(N*M)，其中N和M是列表大小。
您可以提出的另一个解决方案是使用计数器类，它的复杂性为O(N+M)：
from collections import Counter
L1,L2 = [3,7,4,2,4,3,1],[4,5,2,2,4,3]
c = list((Counter(L1) & Counter(L2)).elements())
print(c) # [3, 4, 4, 2]Stack Overflow用户
发布于 2021-09-19 21:46:34
正如我在问题注释中提到的那样，无论是sets还是您的循环解决方案都不能处理每个列表中的重复项，所以我将假设没有任何副本。
下面是一个生成器版本，它对两个列表进行排序，然后合并它们(使用heapq.merge)。这样，两个列表中共有的值一起出现，因此，如果值与前面的相同，则生成一个值：
def common_elements1(list1, list2):
list1.sort()
list2.sort()
merged = merge(list1, list2)
prev = next(merged, None)
for x in merged:
if x == prev:
yield x
prev = x海象列表的比较版本：
def common_elements2(list1, list2):
list1.sort()
list2.sort()
merged = merge(list1, list2)
prev = next(merged, None)
return [x for x in merged
if x == prev or not [prev := x]]或使用itertools.groupby
def common_elements3(list1, list2):
list1.sort()
list2.sort()
merged = merge(list1, list2)
return [x for _, [_, *g] in groupby(merged)
for x in g]所有带有测试的代码：在网上试试！
Stack Overflow用户
发布于 2021-09-19 22:04:14
我相信你的问题的答案是双指针
这样做的目的是对这两个列表进行排序，并在l1开头有一个指针，在l2开头有一个j，每次比较这两个元素时，将最小元素的指针向前移动，直到其中一个元素到达末尾为止。
def findCommon(l1,l2):
l1.sort()
l2.sort()
i= 0
j = 0
res = []
while i < len(l1) and j < len(l2):
if l1[i] == l2[j]:
res.append(l1[i])
if l1[i] < l2[j]:
i += 1
else:
j += 1
return res页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/69247013
复制相关文章
相似问题
腾讯云开发者
