41. First Missing Positive

# Hard

交换后的效果，下脚标+1=元素，即[1,2,3,-5,0]

Python

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        # sort the list, make postivie integers in order from index of 0
        # negative or duplicated elements are at the end
        i = 0
        while i < len(nums):
            if nums[i] <= 0 or nums[i]-1 >= len(nums) or nums[i] == i+1 or nums[i] == nums[nums[i]-1]:
                i += 1
            else:
                otherIndex = nums[i]-1
                temp = nums[i]
                nums[i] = nums[otherIndex]
                nums[otherIndex] = temp
            
        # find the missing one
        for i in range(len(nums)):
            if nums[i] != i + 1:
                return i+1
            
        return len(nums)+1