Swift如何让我的函数超过O（n）？

Question

我正在尝试解决一个LeetCode问题，该问题要求：

给定一个整数数组，其中1 ≤ a[i] ≤ n（n = 数组大小），一些元素出现两次，其他元素只出现一次。

找到所有在此数组中未出现的[1，n]包括的元素。

我的解决方案是：

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)。

- John Doe

---

nums.contains(i) 的时间复杂度是 O(n)，而你又将它嵌入到一个时间复杂度也为 O(n) 的 for 循环里，因此总时间复杂度为 O(n^2)。 - Cristik

@Cristik 没有办法啊！谢谢！ - John Doe

Answer 1

如果我没有漏掉任何东西，你的算法复杂度为O(n^2)。

首先，你需要遍历数组中的每个元素，这是O(n)，但是对于每个元素，你调用了“contains”方法，该方法必须再次遍历所有元素，最终得到O(n^2)的复杂度。

由于这是针对Leetcode的问题，我不会告诉你解决方案。

- kiecodes

---

不怪怪的！谢谢你的帮助！！（是的，请不要给我答案！！） - John Doe