我决定学习 python,并使用 CodeFight 进行训练。第一个 Interview Practice 练习是关于找到数组的第一个副本并返回它,如果没有则返回 -1。这是我写的代码:
def firstDuplicate(a):
b=[]
print(len(a))
for i in range(len(a)):
if a[i] in b:
return(a[i])
elif a[i] not in b and i == (len(a)-1):
return(-1)
else:
b.append(a[i])
我通过了除最后 3 个测试之外的所有测试。我说我的程序执行时间超过 4000 毫秒。我猜数组很长,副本在最后。我怎样才能减少这个执行时间?提前致谢。
最佳答案
您当前的解决方案使用 list
进行簿记,in
成员测试在时间上始终是线性的。您应该改为考虑使用 set
,或将值计数保存在 Counter
中。
这两种情况的想法是,如果没有必要,不要遍历整个列表。通过一点额外的空间,您可以提高性能。
def firstDuplicateSet(a):
seen = set()
for i in a:
if i in seen:
return i
seen.add(i)
return -1
from collections import Counter
def firstDuplicateCounter(a):
c = Counter()
for i in a:
c[i] += 1
if c[i] > 1:
return i
return -1
关于python - 查找数组的第一个副本,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/46513358/