以有效的方式从数组中查找缺失的编号

Question

我正在尝试找到一种有效的方法来解决从数组中查找缺失数字的问题。我按照以下方式实现了 O(n)。请编写任何可以有效解决此问题的代码，仅供学习之用。

func findMissingNo(arrA: [Int]) -> [Int] {
    let firstIndex = arrA.first ?? 0
    let lastIndex = arrA.last ?? 0
    let rslt = Array(firstIndex...lastIndex)
    let missingNoArray = rslt.filter{ !arrA.contains($0)}
    return missingNoArray
}
findMissingNo(arrA: [11,12,14,15,16,18]) // Prints [13, 17] by looping 9 times

Answer 1

快速编写和测试（就代码的性能而言，但不是可能的边缘情况/错误，例如，如果数组是

0...10

，它将不起作用，但我会让你继续工作边缘情况，因为我主要关注主要情况，在编辑和问题结束期间可能涵盖的情况）

您当前的代码：

func findMissingNo(arrA: [Int]) -> [Int] {
    let firstIndex = arrA.first ?? 0
    let lastIndex = arrA.last ?? 0
    let rslt = Array(firstIndex...lastIndex)
    let missingNoArray = rslt.filter{ !arrA.contains($0)}
    return missingNoArray
}
let numberArray = [11,12,14,15,18]
let missing1 = findMissingNo(arrA: numberArray)
print("Missing1: \(missing1)")

我的尝试：

func findMissingNo2(arrA: [Int]) -> [Int] {
    var missingNumbers: [Int] = []
    guard arrA.count > 2 else { return missingNumbers }
    for i in 0...arrA.count-2 {
        var current = arrA[i]
        let next = arrA[i+1]
        if next != current + 1 {
            current += 1
            while current != next {
                missingNumbers.append(current)
                current += 1
            }
        }
    }
    return missingNumbers
}


let missing2 = findMissingNo2(arrA: numberArray)
print("Missing1: \(missing2)")

创建大批量：

var array = Array(0...1000)
for _ in 0...10 {
    if let index = array.indices.randomElement() {
        let value = array.remove(at: index)
        print("removed: \(value)") //To check just in case that's the good value returned by the methods
    }
}

测试：

let date1 = Date()
for _ in 0...100 {
    let missing = findMissingNo(arrA: array)
    print(missing)
}
print(Date().timeIntervalSince(date1)) //18.617565035820007

let date2 = Date()
for _ in 0...100 {
    let missing = findMissingNo2(arrA: array)
    print(missing)
}
print(Date().timeIntervalSince(date2)) //0.09566605091094971

print("---End")
print("")

当时，我得到：

18.857954025268555

与

0.09159696102142334

，一个很大的因子差异（约 200 倍）。

为什么差别这么大？

因为

let missingNoArray = rslt.filter{ !arrA.contains($0)}

这意味着：
对于结果中的每个数字，检查 arrayA 是否包含该数字。
->
对于结果中的每个数字，对于 arrayA 中的每个数字（具有停止条件，因此这不是完整迭代，但就复杂性而言“几乎”）检查是否存在匹配...
这里有一个“double”（实际上不是 double，而是 n？）迭代，您错过了。

我首先用更大的值（从“0到100000”的数组）进行测试，但是花费了太多时间，随着“值的数量较少”，差异已经可以看到。

相反，您可以使用

Set

:

let missingNoArray = Array(Set(rslt).subtracting(Set(arrA))).sorted()

在我的测试中它比你的方法更快（时间性能是我的解决方案（0.21 ~ 0.22）的两倍），但仍然比你的快得多。 我添加了

sorted()

，这在您的解决方案中可能重要也可能不重要，但会增加时间消耗，因为

Set

未订购。

对于边缘情况（即：

[3]

、

[3, 4]

、

[3, 8]

）

guard arrA.count > 2 else { return missingNumbers }

==>

guard !arrA.isEmpty else { return [] }
guard arrA.count > 2 else {
    if arrA[0] + 1 >= arrA[1] {
        return []
    } else {
        return Array((arrA[0] + 1)...arrA[1]).dropLast() //Because last will be arrA[1] which is present)
    }
}

Answer 2

给出一个由N个不同整数组成的数组A。该数组包含 [1..(N + 1)] 范围内的整数，这意味着恰好缺少一个元素。

我的解决方案是：

public func solution(_ A : inout [Int]) -> Int {
    var missingNumber = A.first ?? 0 
    var tempArray = [Int](repeating: 0, count: A.count + 2)
    for element in A {
        tempArray[element] = 1
    }
    for (index, tempElement) in tempArray.enumerated() {
        if index == 0 {
            continue
        }
        if tempElement == 0 {
            missingNumber = index
            break
        }
    }
    return missingNumber
}