41. First Missing Positive

题目

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

For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

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

题意

主要是限制时间复杂度和空间复杂度
先将正负分开，对正数进行分析，正常情况下是下标值+1等于元素值，如果元素值-1后大于数组长度，则遍历下一个元素，否则直到该元素满足条件，才遍历下一个元素；最后找出第一个缺失的元素即可，时间复杂度为O(n)

关于重复的元素解决问题我是使用了set

python实现

class Solution(object):
    def firstMissingPositive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums=list(set(nums))
        #正负分开
        j=len(nums)-1
        i=0
        while i<=j:
            if nums[i]<=0:
                temp=nums[j]
                nums[j]=nums[i]
                nums[i]=temp
                j-=1
            else:i+=1
        #print(nums)
        j=0
        while j<i:
            if nums[j]==j+1:
                j+=1
            elif 0<=nums[j]-1<len(nums):
                temp = nums[nums[j] - 1]
                nums[nums[j] - 1] = nums[j]
                nums[j] = temp
            else:j+=1
        #print(nums)
        j=0
        while j<i:
            if nums[j]!=j+1:
                return j+1
                break
            j+=1
        return j+1