解决Python中的“firstDuplicate”问题

Question

我正在尝试解决来自 codesignal.com 的以下挑战：

\n\n

给定一个仅包含 1 到 a.length 范围内的数字的数组 a，找到第二次出现具有最小索引的第一个重复数字。换句话说，如果有超过 1 个重复数字，则返回第二次出现的索引比另一个数字第二次出现的索引小的数字。如果不存在这样的元素，则返回-1。

\n\n

例子

\n\n

For a = [2, 1, 3, 5, 3, 2]，输出应该是\n firstDuplicate(a) = 3。

\n\n

有 2 个重复项：数字 2 和 3。第二次出现的 3 的索引比第二次出现的 2 的索引小，因此答案是 3。

\n\n

对于a = [2, 4, 3, 5, 1]，输出应为\n firstDuplicate(a) = -1。

\n\n

执行时间限制为4秒。

\n\n

保证的约束是：

\n\n

1 \xe2\x89\xa4 a.length \xe2\x89\xa4 10^5， 和

\n\n

1 \xe2\x89\xa4 a[i] \xe2\x89\xa4 a.length

\n\n

所以我的代码是：

\n\n

def firstDuplicate(a):\n    b = a\n    if len(list(set(a))) == len(a):\n        return -1\n\n    n = 0\n    answer = -1\n    starting_distance = float("inf")\n\n    while n!=len(a):\n        value = a[n]\n\n        if a.count(value) > 1:\n\n            place_of_first_number = a.index(value)\n\n            a[place_of_first_number] = \'string\'\n\n            place_of_second_number = a.index(value)\n\n            if place_of_second_number < starting_distance:\n\n                starting_distance = place_of_second_number\n                answer = value\n\n            a=b\n        n+=1\n        if n == len(a)-1:\n            return answer \n    return answer\n

\n\n\n\n

在该网站进行的 22 项测试中，我通过了所有测试，直到#21，因为测试列表很大，并且执行时间超过了 4 秒。有哪些技巧可以减少执行时间，同时保持代码大致相同？

\n

Answer 1

正如@erip在评论中指出的那样，您可以迭代列表，将项目添加到集合中，如果该项目已经在集合中，则它是具有最低索引的重复项，因此您可以简单地返回该项目; 或者如果到达循环末尾而没有找到重复项则返回 -1：

def firstDuplicate(a):
    seen = set()
    for i in a:
        if i in seen:
            return i
        seen.add(i)
    return -1