如何在Python中高效查找两个大列表的有序无重复公共元素

针对处理大型整数列表的公共元素查找需求，最优方案是通过集合的O(1)成员查询特性替代嵌套循环的O(m)查询，将整体时间复杂度从O(n*m)降至O(n+m)，同时满足「保留第一个列表顺序」和「结果无重复」的要求。

实现思路 #

1. 将第二个列表转换为集合：集合的成员查询操作时间复杂度为O(1)，这是性能提升的核心。
2. 遍历第一个列表时维护一个「已添加元素集合」：避免结果中出现重复项，同时保证只保留元素在第一个列表中首次出现的顺序。
3. 遍历过程中筛选符合条件的元素：仅当元素存在于第二个列表的集合中，且未被添加到结果里时，才将其加入结果列表。

代码实现 #

def find_common_elements(list1, list2):
    # 将第二个列表转为集合，O(m)时间复杂度
    set2 = set(list2)
    # 记录已添加到结果中的元素，避免重复
    seen = set()
    result = []
    # 遍历第一个列表，O(n)时间复杂度
    for num in list1:
        if num in set2 and num not in seen:
            result.append(num)
            seen.add(num)
    return result

方案优势 #

• 性能高效：对于两个长度分别为n和m的大型列表，总操作次数仅为n+m次，远低于嵌套循环的n*m次，处理百万级列表时差距尤为明显。
• 逻辑清晰：同时满足「顺序保留」和「去重」的要求，无需额外排序或去重步骤。
• 内存可控：集合的内存开销远低于嵌套循环的重复查询消耗，适合处理大规模数据。

内容的提问来源于stack exchange，提问作者Siva revanth Kodavali