从数组中找到缺失的有效方法

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([=10=])}
    return missingNoArray
}
findMissingNo(arrA: [11,12,14,15,16,18]) // Prints [13, 17] by looping 9 times

Answer 1

快速编写和测试（根据您的代码的时间性能，但不是可能的边缘 cases/mistakes，例如，如果数组是 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([=10=])}
    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 vs 0.09159696102142334，一个很大的因数差异（~200 倍）。

为什么差别这么大？

因为

let missingNoArray = rslt.filter{ !arrA.contains([=14=])}

意思是：
对于结果中的每个数字，检查 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)
    }
}

从数组中找到缺失的有效方法

Find the Missing no from an array the efficient way

arrays

big-o

ios

swift