Array

041. First Missing Positive

Given an unsorted integer array, find the smallest missing positive integer.
就是 给一个整数数组，找到数组中缺少的最小正整数
我的理解：
如果这个数组中没有1，那么这个最小正整数就应该是1，
如果数组里面有1，那么当第一次有连续两个整数之间差值大于1时(前提是数组有序)，缺失的最小正整数应该为前一个数加1，否则，如果数组是连续整数，那么缺失的最小值为最后一个数+1
然后就写出了一段很蠢的代码

class Solution:
    def firstMissingPositive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums.sort()
        if 1 not in nums:
            return 1
        elif len(nums)==1:
            return 2
        else:
            for i in range(len(nums)-1):
                if nums[i]<0:
                    continue
                if nums[i]<nums[i+1]-1:
                    return nums[i]+1
            return nums[-1]+1

参考了别人的代码，发现我的想法太直接了，傻呀
这段代码的核心思想是，遍历整个数组使得第i个位置上存放的值是i+1，然后再遍历一遍，返回第一个不符合前述条件的i+1

class Solution:
    def firstMissingPositive(self, A):
        i = 0
        while i < len(A):
            if A[i] > 0 and A[i] - 1 < len(A) and A[i] != A[A[i]-1]:
                A[A[i]-1], A[i] = A[i], A[A[i]-1]
            else:
                i += 1

        for i, integer in enumerate(A):
            if integer != i + 1:
                return i + 1
        return len(A) + 1