为什么这个答案会通过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

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

空间复杂度为O（1），因为只创建了i

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

Answer 1

你有两个循环在一起。你有一个从1到max(nums)+2的迭代过程，在这个if i not in nums:内部，它在nums上迭代。因此，您的复杂性将类似于O(n^2)。你知道吗