Swift 我的函数如何超过 O(n)？

Question

我正在尝试解决要求的 leetcode 问题

Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements of [1, n] inclusive that do not appear in this array.

我的解决方案是:

func findDisappearedNumbers(_ nums: [Int]) -> [Int] {
    var returnedArray = [Int]()

    if nums.isEmpty == false {
        for i in 1...nums.count {
            if nums.contains(i) == false {
                returnedArray.append(i)
            }
        }
    } else {
        returnedArray = nums
    }
    return returnedArray
}

但是，leetcode 告诉我，我的解决方案是“超出时间限制”

我的解决方案不应该是 O(n) 吗？我不确定我在哪里让它大于 O(n)。

Answer 1

如果我没有遗漏任何东西，你的算法是 O(n^2)。

首先，您遍历数组的每个元素，即 O(n)，但是对于每个元素，您调用 contains，它必须再次遍历所有元素，最终得到 O(n) (n^2).

我不告诉你解决方案，因为它是针对 leetcode 的。