如何高效查找整数数组中缺失的数字 现有O(n)实现求优化方案

首先明确你当前实现的性能问题：

你以为现有代码的时间复杂度是O(n)，但实际存在很大优化空间：filter的遍历次数等于数组首尾元素的差值+1，而Array.contains()单次调用的时间复杂度是O(n)，整体复杂度实际为O(n*(end-start))，当数组首尾差值较大时性能会非常差。

以下是两种不同场景的优化实现： #

方案1：利用Set降低查询复杂度（适用于无序数组） #

将原数组先转成Set，元素存在性查询的复杂度直接降到O(1)，整体时间复杂度优化为O(n + (end-start))，相比原实现提升非常明显。

func findMissingNo(arrA: [Int]) -> [Int] {
    guard !arrA.isEmpty else { return [] }
    let minVal = arrA.min()!
    let maxVal = arrA.max()!
    let numSet = Set(arrA)
    return (minVal...maxVal).filter { !numSet.contains($0) }
}

方案2：单次遍历有序数组（最优解，纯O(n)时间复杂度） #

如果你的输入数组默认是升序排列的（你给出的示例输入就属于有序场景），不需要额外存储结构，直接遍历一次数组对比相邻元素即可，差大于1的区间就是缺失的数字，空间复杂度仅为O(1)（不计结果存储占用）。

func findMissingNo(arrA: [Int]) -> [Int] {
    guard arrA.count > 1 else { return [] }
    var missingNums: [Int] = []
    for i in 1..<arrA.count {
        let prevNum = arrA[i-1]
        let currentNum = arrA[i]
        if currentNum - prevNum > 1 {
            missingNums.append(contentsOf: (prevNum+1)..<currentNum)
        }
    }
    return missingNums
}

// 测试调用
findMissingNo(arrA: [11,12,14,15,16,18]) // 输出 [13, 17]

内容的提问来源于stack exchange，提问作者Swiosift