原题

给出一个无序的正数数组，找出其中没有出现的最小正整数。

如果给出 [1,2,0], return 3 如果给出 [3,4,-1,1], return 2
只允许时间复杂度O(n)的算法，并且只能使用常数级别的空间。

解题思路

• 类似于桶排序的思路，对于每一个整数，我们按照一定的规则放到相应的位置上，最后再去检查如果指定位置的数不存在，即为没有出现的最小正整数
• 规则：1放在array[0]，2放在array[1]，以此类推
  对于[3, 4, -1, 1]，运行最终结果为[1, -1, 3, 4]所以检查到array[1]时，2不存在，2即为没有出现的最小正整数
• 注意，遍历数组是，对于每一位要while循环至该位置的数字放到正确的位置为止

while nums[i] <= len(nums) and nums[i] > 0 and nums[nums[i] - 1] != nums[i]:
    nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]

完整代码

class Solution(object):
    def firstMissingPositive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 1
            
        for i in range(len(nums)):
            while nums[i] <= len(nums) and nums[i] > 0 and nums[nums[i] - 1] != nums[i]:
                nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
        
        for i in range(len(nums)):
            if nums[i] != i + 1:
                return i + 1
        return len(nums) + 1