有效地查找列表中的重复项

Question

我有下面的函数，它在数组中搜索重复的条目，然后返回重复项的列表。我想加快这段代码的速度，有人能建议一种更有效的方法吗？

代码：

def findDupe(array):
    dupelist = []
    for i in range(len(array)):
        for j in range(len(array)):
            comp1 = array[i]
            comp2 = array[j]
            if comp1 == comp2 and i!=j:
                if comp2 not in dupelist:
                    dupelist.append(comp2)
    return dupelist

Answer 1

这里的想法是在线性时间内进行一次扫描。您可以使用计数器来执行此操作。这个想法是对每个元素进行计数，然后返回所有被多次计数的元素。

from collections import Counter

def get_duplicates(array):
    c = Counter(array)
    return [k for k in c if c[k] > 1] 

上面的方法在复杂性上是线性的，但是对输入进行了两次传递 - 一次是为了计数（这是由Counter构造函数抽象出来的），另一个是返回列表 comp 中的非唯一值。您可以使用语句对此进行一些优化yield，并在找到重复项时返回它们。

def get_duplicates(array):
    c = Counter()
    seen = set()
    for i in array: 
        c[i] += 1
        if c[i] > 1 and i not in seen:
            seen.add(i)
            yield i

这会导致强制if检查和 a 形式的额外空间set，但您可以将两次通过减少为一次。