python - 为什么这个答案通过了 Leetcode Q41

Question

这里的问题：https ://leetcode.com/problems/first-missing-positive/description/

您的算法应该在 O(n) 时间内运行并使用恒定的额外空间。

我有一个非常幼稚的解决方案通过了，因为这个问题被标记为困难并且大多数人在讨论中的解决方案要复杂得多。

def firstMissingPositive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if nums == []:
            return 1
        for i in range(1, max(nums)+2):
            if i not in nums:
                return i

findmax使用 O(n)，因为一旦找到丢失的正数，循环就会停止，它将是 O(n)。range在 py3 中返回一个可迭代的，for 语句的每个循环都会即时生成下一个数字。所以时间复杂度应该是O(n)

i空间复杂度为O(1)，因为只有

我想 OJ 只检查正确性，但不检查空间/时间复杂度。但是我看不出这个解决方案是怎么错的。有人可以指出吗？

标签： pythonalgorithm

Answer 1

你有两个相互内部的循环。你有一个从1到迭代max(nums)+2的if i not in nums:迭代nums。所以你的复杂性将类似于O(n^2).