O(1) space can usually be done by mutating input list.
The idea is try moving elements within the array such that number
n is at index
n-1. Then loop from
input[i] is None then
i + 1 is missing. Otherwise return
len(input) + 1
Few points to note:
n-1is out of array boundary, we can't find a new index to move to, just skip.
nis already in its correct position
n - 1, do nothing.
def firstMissingPositive(self, nums): """ :type nums: List[int] :rtype: int """ for i in range(len(nums)): tmp, nums[i] = nums[i], None while tmp is not None and 0 <= tmp-1 < len(nums) and tmp != nums[tmp-1]: nums[tmp-1], tmp = tmp, nums[tmp-1] for i in range(len(nums)): if nums[i] is None: return i+1 return len(nums) + 1