这里的问题: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只检查正确性,而不检查空间/时间复杂性。但是我看不出这个解决方案是怎么错的。有人能指出吗?你知道吗
你有两个循环在一起。你有一个从
1
到max(nums)+2
的迭代过程,在这个if i not in nums:
内部,它在nums
上迭代。因此,您的复杂性将类似于O(n^2)
。你知道吗带有嵌套隐式循环
if i not in nums:
的显式循环for i in range(1, max(nums)+2):
不是O(n)
;)相关问题 更多 >
编程相关推荐