python - 查找数组的第一个副本

Question

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

Answer 1

您当前的解决方案使用 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