解决 Python 中的“firstDuplicate”问题

Question

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

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

例子

For 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 秒。有什么技巧可以减少执行时间，同时保持代码大致相同？

Answer 1

您可以遍历列表，将项目添加到集合中，如果该项目已经在集合中，则它是具有最低索引的重复项，因此您可以简单地返回该项目; 或者如果您到达循环末尾而没有找到重复项，则返回 -1：def firstDuplicate(a):&nbsp; &nbsp; seen = set()&nbsp; &nbsp; for i in a:&nbsp; &nbsp; &nbsp; &nbsp; if i in seen:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return i&nbsp; &nbsp; &nbsp; &nbsp; seen.add(i)&nbsp; &nbsp; return -1

Answer 2

创建一个新集合并在新列表中找到它，如果它返回元素：def firstDuplicate(a):&nbsp; &nbsp; dup = set()&nbsp; &nbsp; for i in range(len(a)):&nbsp; &nbsp; &nbsp; &nbsp; if a[i] in dup:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return a[i]&nbsp; &nbsp; &nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; dup.add(a[i])&nbsp; &nbsp; return -1

Answer 3

这只是一个想法，我没有验证它，但它应该可以工作。似乎没有内存限制，只有时间限制。因此，使用空间来交易时间可能是一种实用的方法。计算复杂度为O(n)。该算法还取决于数字范围在 1 到 之间的条件len(a)。def first_duplicate(a):&nbsp; &nbsp; len_a = len(a)&nbsp; &nbsp; b = [len_a + 1] * len_a&nbsp; &nbsp; for i, n in enumerate(a):&nbsp; &nbsp; &nbsp; &nbsp; n0 = n - 1&nbsp; &nbsp; &nbsp; &nbsp; if b[n0] == len_a + 1:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; b[n0] = len_a&nbsp; &nbsp; &nbsp; &nbsp; elif b[n0] == len_a:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; b[n0] = i&nbsp; &nbsp; min_i = len_a&nbsp; &nbsp; min_n = -1&nbsp; &nbsp; for n0, i in enumerate(b):&nbsp; &nbsp; &nbsp; &nbsp; if i < min_i:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; min_i = i&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; min_n = n0 + 1&nbsp; &nbsp; return min_n更新：此解决set()方案不如@blhsing的解决方案快。但是，如果它是用 C 实现的，可能就不一样了——这有点不公平，因为它set()是一个内置函数，它是用 C 实现的，作为 CPython 的其他核心函数。