41. First Missing Positive

Given an unsorted integer array, find the smallest missing positive integer.

Example 1:

Input: [1,2,0]
Output: 3

Example 2:

Input: [3,4,-1,1]
Output: 2

Example 3:

Input: [7,8,9,11,12]
Output: 1

Note:

Your algorithm should run in O(n) time and uses constant extra space.

Code：

class Solution(object):
    def firstMissingPositive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n, i = len(nums), 0
        if n == 0: return 1
 
        while i < n:
            # 获取当前位置的数据
            w = nums[i] - 1  
            # 0 < nums[i] <= n 判断是否出界
            if 0 < nums[i] <= n and nums[i] != nums[w]: 
                # nums[i] != nums[w] 如果相等或者是本身就没必要替换了，避免死循环
                nums[i], nums[w] = nums[w], nums[i]      
            # 当前位置上的数，没有找到合适的位置，进行下一个位置
            else:
                i += 1  
         # 遍历返回
        for i in range(n): 
            if i + 1 != nums[i]:
                return i + 1
        return n + 1