解决 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):

    seen = set()

    for i in a:

        if i in seen:

            return i

        seen.add(i)

    return -1

Answer 2

创建一个新集合并在新列表中找到它，如果它返回元素：

def firstDuplicate(a):

    dup = set()

    for i in range(len(a)):

        if a[i] in dup:

            return a[i]

        else:

            dup.add(a[i])

    return -1

Answer 3

这只是一个想法，我没有验证它，但它应该可以工作。似乎没有内存限制，只有时间限制。因此，使用空间来交易时间可能是一种实用的方法。计算复杂度为O(n)。该算法还取决于数字范围在 1 到 之间的条件len(a)。

def first_duplicate(a):

    len_a = len(a)

    b = [len_a + 1] * len_a

    for i, n in enumerate(a):

        n0 = n - 1

        if b[n0] == len_a + 1:

            b[n0] = len_a

        elif b[n0] == len_a:

            b[n0] = i

    min_i = len_a

    min_n = -1

    for n0, i in enumerate(b):

        if i < min_i:

            min_i = i

            min_n = n0 + 1

    return min_n

更新：

此解决set()方案不如@blhsing的解决方案快。但是，如果它是用 C 实现的，可能就不一样了——这有点不公平，因为它set()是一个内置函数，它是用 C 实现的，作为 CPython 的其他核心函数。