Python查找两列表共同元素的for循环实现 如何通过排序降低时间复杂度

原有实现的性能问题 #

你之前写的for循环版本时间复杂度为O(nm)*：每次执行element in list2时都需要遍历list2判断元素是否存在，当两个列表数据量较大时性能会急剧下降。

排序+双指针优化思路 #

按照面试官给出的排序提示，可以用双指针法做到不用遍历两个列表的所有元素，具体逻辑如下：

• 先对两个列表分别做升序排序，排序总时间复杂度为O(n log n + m log m)（n、m分别为两个列表的长度）
• 初始化两个指针分别指向两个列表的起始位置，按照如下规则移动指针：
  • 两指针指向元素相等时，该元素为共同元素，加入结果集，两个指针同时后移一位
  • 指针1指向的元素更小，仅后移指针1（排序后更小的元素不可能在列表2的后续位置找到匹配项）
  • 指针2指向的元素更小，仅后移指针2
  • 任意一个指针超出列表长度时直接终止循环

实现代码 #

def common_elements(list1, list2):
    list1.sort()
    list2.sort()
    p1 = p2 = 0
    result = []
    while p1 < len(list1) and p2 < len(list2):
        if list1[p1] == list2[p2]:
            result.append(list1[p1])
            p1 += 1
            p2 += 1
        elif list1[p1] < list2[p2]:
            p1 += 1
        else:
            p2 += 1
    return result

优化效果说明 #

• 整体时间复杂度为O(n log n + m log m)，数据量越大相比原有O(n*m)的实现优势越明显
• 该方案可以保留重复的共同元素，比如list1存在2个3、list2存在3个3时，结果会返回2个3，如果用set.intersection实现会自动去重仅返回1个3
• 如果允许对结果去重，直接使用set.intersection的方案时间复杂度为O(n+m)，性能更优

内容的提问来源于stack exchange，提问作者LLL