使用 for 循环 python 在两个列表中查找共同项 - 降低时间复杂度

Question

在一次采访中，我被要求找出 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 循环之后，面试官问我是否有任何方法可以通过不必遍历列表中的每个项目来降低时间复杂度。他还暗示我可以先对列表进行排序。我无法回答这个问题，我仍在努力解决这个问题。我该如何解决这个问题？

Answer 1

正如我在问题评论中提到的，集和循环解决方案都不能处理每个列表中的重复项，因此我假设它保证没有任何重复项。

这是一个生成器版本，它对两个列表进行排序然后合并它们（使用 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]

所有带测试的代码：Try it online!

Answer 2

我相信你的问题的答案是双指针

思路是对两个列表进行排序，在l1的开头有一个指针i，在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

Answer 3

您可以结合使用 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 是列表大小

您可能提出的另一种解决方案是使用 Counter class，其复杂度为 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]

使用 for 循环 python 在两个列表中查找共同项 - 降低时间复杂度

find common items in two lists using for loop python - reduce time complexity

python

for-loop

list

time-complexity