查找数组的第一个副本 [英] Finding the first duplicate of an array

问题描述

我决定学习 Python 并使用 CodeFight 进行训练.第一次面试练习是关于找到数组的第一个副本并返回它，如果没有则返回 -1.这是我写的代码:

I've decided to learn python and I use CodeFight to train. The first Interview Practice exercice is about finding the first duplicate of an array and returning it or retruning -1 if there isn't any. This is the code I wrote:

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

I pass all the tests except the last 3. I says that my program takes longer than 4000ms to execute. I guess the array is very long and the duplicate is at the end. How can I reduce this execution time ? Thanks in advance.

推荐答案

您当前的解决方案使用 list 进行簿记，in 成员资格测试一直在进行在时间上是线性的.您应该考虑使用 set，或者在 Counter 中保留值的计数.

Your current solution uses a list to do book-keeping, the in membership test is always going to be linear in time. You should instead consider using a set, or keeping counts of values in a Counter.

这两种情况下的想法是，如果没有必要，不要遍历完整列表.只需一点额外的空间，您就可以提高性能.

The idea in both cases is not to iterate through the complete list if not necessary. With a little extra space, you improve performance.

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

这篇关于查找数组的第一个副本的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！