The result will be between
len(nums)+1 including, so we can use the indexes of the list. But there's no need to swap, sort or remove any elements. We can remember that number
k appeared in nums by changing
(k-1)th number to float.
Runtime: 49 ms. If someone can make this idea run faster, I'd like to hear about it.
class Solution(object): def firstMissingPositive(self, nums): :type nums: List[int] :rtype: int for num in nums: if num>0: try: #we don't care about numbers bigger than len(nums) nums[int(num)-1] *= 1.0 except: pass for i in xrange(len(nums)): if type(nums[i]) != float: return i+1 #there were all the numbers between 1 and len(nums) return len(nums)+1