```
class Solution(object):
def firstMissingPositive(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
end = len(nums)
if end == 0: return 1
i = 0
while i < end:
if i == nums[i]-1:
i += 1
elif nums[i] < 1 or nums[i] > end or nums[nums[i]-1] == nums[i]:
nums[i] = nums[end-1]
end -= 1
else:
n = nums[nums[i]-1]
nums[nums[i]-1] = nums[i]
nums[i] = n
return i+1
```