我正在尝试解决来自 codesignal.com 的以下挑战:
给定一个仅包含 1 到 a.length 范围内数字的数组 a,找到第一个重复数字,其中第二次出现的数字具有最小索引。换句话说,如果有超过 1 个重复的数字,则返回第二次出现的索引小于另一个数字的第二次出现的索引的数字。如果没有这样的元素,返回-1。
例子
对于 a = [2, 1, 3, 5, 3, 2],输出应该是 firstDuplicate(a) = 3。
有 2 个重复项:数字 2 和 3。第二次出现的 3 的索引比第二次出现的 2 的索引小,所以答案是 3。
对于 a = [2, 4, 3, 5, 1],输出应该是 firstDuplicate(a) = -1。
执行时间限制为 4 秒。
保证的约束是:
1 ≤ a.length ≤ 10^5,并且
1 ≤ a[i] ≤ a.length
所以我的代码是:
def firstDuplicate(a):
b = a
if len(list(set(a))) == len(a):
return -1
n = 0
answer = -1
starting_distance = float("inf")
while n!=len(a):
value = a[n]
if a.count(value) > 1:
place_of_first_number = a.index(value)
a[place_of_first_number] = 'string'
place_of_second_number = a.index(value)
if place_of_second_number < starting_distance:
starting_distance = place_of_second_number
answer = value
a=b
n+=1
if n == len(a)-1:
return answer
return answer
在该站点进行的 22 项测试中,我通过了所有测试,直到 #21,因为测试列表很大并且执行时间超过 4 秒。有哪些技巧可以减少执行时间,同时保持代码大致相同?
请您参考如下方法:
正如@erip 在评论中指出的那样,您可以遍历列表,将项目添加到集合中,如果该项目已经在集合中,则它是具有最低索引的副本,因此您可以简单地返回;或者,如果您到达循环末尾而没有找到重复项,则返回 -1:
def firstDuplicate(a):
seen = set()
for i in a:
if i in seen:
return i
seen.add(i)
return -1
