如何以最有效的方式在列表中找到重复的内容？

Question

假设我有一个列表：

l = ['a', 'b', 'c', 'd', 'e', 'f', 'e']

如您所见，索引4和索引6是重复的。我的问题是：什么是最有效的方法来查看列表中是否有重复的内容？在

选项1：

^{pr2}$

如果输出为false，则其中有一个值不止一次。在

选项2：

output = True
for i in l:
  if l.count(i) > 1:
    output = False

如果输出为false，则其中有一个值不止一次。在

问题：

1. 最有效的方法是什么？

2. 如何计算这两个（或更多）的O符号选择？

谢谢！在

Answer 1

循环并收集集合中的可见项。在

一旦发现第一个副本，请注意break。在极端情况下（没有重复），您将循环列表一次并构建一个包含每个列表项的集合。在

l = ['a', 'b', 'c', 'd', 'e', 'f', 'e']
seen = set()

for x in l:
    if x in seen:
        print("seen '{}' already, done".format(x))
        # As soon as find find the first duplicate, break.
        break
    seen.add(x)

输出：

^{pr2}$

Answer 2

选项1很快。

因为set方法使用散列，len方法需要O（1）时间。在

所以这是任何人都能做到的最快的方法。在

https://wiki.python.org/moin/TimeComplexity

Answer 3

关于计算O（）值：

选项1做4件事：创建一个集合，得到它的长度，得到列表的长度，然后比较它们。其中，创建集合必须至少是O（n），其他的至多是O（n），因此效率主要取决于集合的创建。我相信Python中集合的实现是这样的：插入平均需要O（1），因此这应该是O（n）。在

选项2包含一个循环。在循环中，调用l.count，它遍历整个列表来计算一个项目发生的次数。所以每次迭代都是O（n）。循环本身每循环n次。总效率O（n*n）。在

是否存在比选项1更快的内容取决于实际数据的特征、长度、重复的可能性、不同项的数量（如果它们都是小写字母，那么长度大于等于26的任何列表都有一个重复项，检查起来非常快）等等。无法回答。但是O（n）真的很难被击败，如果复制很少，那么通常所有的项目都必须被检查，这就必然是O（n）。在