高效查找列表中的重复项

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

检查和

set

形式的额外空间，但您可以将两次通过减少为一次。

Answer 2

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

1. 如上所述，在 Set 中存储元素可以提供平均复杂度 θ(n)，但要求元素可哈希（Python 中的 Set 是通过哈希表实现的，请参阅 https://wiki.python.org/moin /时间复杂度）
2. 如果您有比较函数，您可以在最坏情况下对列表进行排序 θ(nlog(n))，然后将列表中的每个元素与下一个元素进行比较。
3. 如果您有比较函数，您还可以实现一个具有（平衡）BST 的集合，并执行与 1 相同的操作，以实现平均复杂度 θ(nlog(n))（在最坏情况下）。

Answer 3

虽然

numpy

还没有

duplicated

方法，但

pandas

有：

df = pd.Series(input_list)

duplicated_values = df[df.duplicated()].to_list()