如何进一步优化这段Python重复元素查找代码以提升性能？

原代码采用两层嵌套循环，时间复杂度为O(n²)，且每次判断元素是否在duplicates列表中是O(k)（k为当前重复元素数量），数据量较大时性能会明显下降。以下是几种高效优化方案：

方案1：利用集合统计出现次数（最优时间复杂度） #

通过一次遍历，用两个集合分别记录已遍历元素和重复元素，集合的查找、插入操作均为O(1)，整体时间复杂度O(n)。

def find_duplicates(lst):
    seen = set()
    duplicates = set()
    for item in lst:
        if item in seen:
            duplicates.add(item)
        else:
            seen.add(item)
    return list(duplicates)

• 集合自动去重，无需额外判断元素是否已在结果中，避免了原代码中列表线性查找的开销。

方案2：用字典计数 #

通过字典统计每个元素的出现次数，再筛选出出现次数≥2的元素，时间复杂度同样为O(n)，适合需要同时获取元素重复次数的场景。

def find_duplicates(lst):
    count = {}
    for item in lst:
        count[item] = count.get(item, 0) + 1
    return [item for item, cnt in count.items() if cnt >= 2]

方案3：排序后遍历（空间优化方向） #

若限制额外空间使用，可先对列表排序，再遍历一次寻找相邻的重复元素，时间复杂度O(n log n)（主要来自排序操作），空间复杂度O(1)（允许修改原列表时）。

def find_duplicates(lst):
    if not lst:
        return []
    lst_sorted = sorted(lst)
    duplicates = set()
    prev = lst_sorted[0]
    for item in lst_sorted[1:]:
        if item == prev:
            duplicates.add(item)
        prev = item
    return list(duplicates)

• 排序后重复元素相邻，只需一次遍历即可定位重复项，用集合存储重复元素避免结果中出现重复值。

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