swift - 加速 Swift CodeFight 挑战

Question

根据 Codefighters:

注意:编写一个具有 O(n) 时间复杂度和 O(1) 额外空间复杂度的解决方案，因为这是您在真实面试中被要求做的事情。

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

示例

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

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

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

这就是我的想法。它可以工作，但在最终测试中失败，因为它运行了超过 4000 毫秒。我坚持我还能做什么。有什么提高速度的想法吗？

func firstDuplicate(a : [Int]) -> Int {
var duplicateIndexArray = [Int]()
for firstIndex in 0..<a.count {

    for secondIndex in 0..<a.count {

        if a[firstIndex] == a[secondIndex] && firstIndex != secondIndex {
            print(firstIndex, secondIndex)
            if !(duplicateIndexArray.contains(firstIndex)){
                duplicateIndexArray.append(secondIndex)
                break
            }
        }
    }
}

// Check for duplicacy
if duplicateIndexArray.count > 0 {
    print(duplicateIndexArray)
    return a[duplicateIndexArray.min()!]
}
return -1

}

Answer 1

O(n) 时间部分很简单，但 O(1) 额外空间有点棘手。通常，哈希集(或您的情况下的位数组)可用于检查某个数字是否多次出现，但这需要 O(n) 额外空间。对于 O(1) 的额外空间，我们可以通过将源数组中的一些数字设为负数，将其用作位数组。

例如，如果数组中的第一个数字是 3，那么我们将位置 3-1 处的数字设为负数。如果数组中的其他数字之一也是 3，我们可以检查位置 3-1 的数字是否为负数。

我没有任何 Swift 经验，所以我会尝试在 pseudocode 中编写一个函数:

function firstDuplicate(a)
    result = -1

    for i = 0 to a.count - 1
         if a[abs(a[i])-1] < 0 then 
             result = a[i] 
             exit for loop
         else
             a[abs(a[i])-1] = -a[abs(a[i])-1]

    // optional restore the negative numbers back to positive
    for i = 0 to a.count - 1
        if a[i] < 0 then 
            a[i] = -a[i]

    return result