查找数组的第一个重复项

我决定学习 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 毫秒。我猜数组很长，重复的在最后。我怎样才能减少这个执行时间？提前致谢。

您当前的解决方案使用list做簿记，in成员资格测试在时间上总是呈线性的。你应该考虑使用set，或对 a 中的值进行计数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