查找数组的第一个副本

Question

我决定学习python,我使用CodeFight进行训练.第一次采访练习是关于找到数组的第一个副本并返回它或者如果没有则返回-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毫秒.我猜数组很长,副本就在最后.如何减少执行时间？提前致谢.

Answer 1

您当前的解决方案使用a list来进行簿记,in会员测试始终是线性的.您应该考虑使用a 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