高效地在列表中查找重复项

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

- user3476463

Answer 1

这里的想法是在线性时间内完成一次扫描。你可以使用计数器来实现这一点。思路是计算每个元素的数量，然后返回那些被计数多次的元素。

from collections import Counter

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

上述方法的复杂度是线性的，但需要对输入进行两次操作——首先进行计数（这由Counter构造函数抽象出来），然后在列表推导式中返回非唯一值。可以通过使用一个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检查，并增加一个set的空间，但您可以将两个通道减少到一个。

- cs95

---

@user3476463，你的函数中有一个循环嵌套另一个循环。这意味着你的函数是二次的，比线性慢得多。 - cs95

@COLDSPEED 你好，我尝试使用 testArray = ['a','b','c','d','e','d'] 和 print get_duplicates(testArray) 打印您的建议结果，但是我得到了以下信息 <generator object get_duplicates at 0x107609eb0> ，如果我想打印结果，我需要做什么？我对生成器不是很熟悉。 - user3476463

@COLDSPEED 谢谢，比之前的版本快多了！ - user3476463

@user3476463 是的！这就是时间复杂度分析的威力。 - cs95

@COLDSPEED 我在原帖中添加了使用%timeit的结果。看起来如果我添加list()，我并没有获得运行时间上的优势。我是否没有正确地使用%timeit？还是有其他我可能遗漏的东西？ - user3476463

Answer 2

你的列表中的元素类型是什么？

1. 像上面解释的那样，将元素存储在Set中可获得平均复杂度Θ(n)，但需要元素是可散列的（Python中的Set是使用哈希表实现的，请参见https://wiki.python.org/moin/TimeComplexity）。
2. 如果你有一个比较函数，你可以以最坏情况Θ(nlog(n))对列表进行排序，然后将列表中的每个元素与下一个进行比较。
3. 如果你有一个比较函数，你还可以使用（平衡）BST实现一个set，并执行与1相同的操作，从而平均复杂度Θ(nlog(n))（在最坏情况下）。

- Quentin Fortier