以有效的方式從陣列中找到缺失的編號

我正在嘗試找到一種有效的方法來解決從陣列中查找缺失數字的問題。我實作了以下方式，它是 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

uj5u.com熱心網友回復：

快速撰寫和測驗（就您的代碼的時間性能而言，但不是就可能的邊緣情況/錯誤而言，例如，如果 array is 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.857954025268555vs 0.09159696102142334，一個很大的因素差異（~200 倍）。

為什么會有這么大的差別？

因為

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

It means:
for each number in result, check if arrayA contains that number.
->
for each number in result, for each number in arrayA (with a stop condition, so it's not a full iteration, but "almost" in term of complexity) check if there is a match...
Here there is a "double" (which is in fact not double, but n?) iteration that you missed.

I tested first with bigger value (array from "0 to 100000"), but it was taking too much time, with that "low number of values", the difference can already be seen.

Instead, you could use a Set:

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

It's faster than you method in my tests, (double my solution (0.21 ~ 0.22) in time performances), but still much faster than yours. I added the sorted(), which may or may not be important in your solution, but will add time consumption since Set aren't ordered.

For the edges cases (ie: [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)
    }
}

標籤：ios 数组 迅速 大O

上一篇：在不運行組合管道的情況下更新屬性

下一篇：如何初始化CollectionViewCellArray中的按鈕