查找列表中是否重复某些内容的最有效方法是什么？

Question

假设我有一个清单:

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

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

选项1:

output = len(set(l)) != len(l):

如果输出为false,则其中有一个值不止一次.

选项2:

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

如果输出为false,则其中有一个值不止一次.

问题:

谢谢!

Answer 1

关于计算O()值:

选项1执行4项操作:创建一个集合,获取其长度,获取列表的长度,然后比较它们.其中,创建集合必须至少为O(n),其他集合最多为O,因此效率由集合创建主导.我相信Python中的集合的实现使得插入平均需要O(1),因此这应该是O(n).

选项2包含一个循环.在循环内部,您调用l.count,遍历整个列表以计算项目发生的次数.所以每次迭代都是O(n).循环本身为循环中的每个项运行,因此n次.总效率为O(n*n).

是否存在比选项1更快的东西取决于您的真实数据的特征,它的长度,重复的可能性,不同项目的数量(如果它们都是小写字母,那么长度> 26的任何列表都有重复,那真的是快速检查)等等.它无法回答.但是O(n)真的很难被击败,如果重复很少,那么通常必须检查所有项目,这必然是O(n).