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

Question

在这里提问:https://leetcode.com/problems/first-missing-positive/description/

Your algorithm should run in O(n) time and uses constant extra space.

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

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

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

空间复杂度为 O(1) 因为只创建了 i

我想 OJ 只检查正确性，但不检查空间/时间复杂度。但是我看不出这个解决方案是错误的。谁能指出来？

Answer 1

显式循环 for i in range(1, max(nums)+2): 带有嵌套隐式循环 if i not in nums: 不是 O (n) ;)