First Missing Positive

Source

• lintcode: First Missing Positive

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

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

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

Python

class Solution:
    # @param A, a list of integers
    # @return an integer
    def firstMissingPositive(self, nums):
        # write your code here
        n = len(nums)

        i=0
        while i<n:
            if nums[i]!=i+1 and nums[i]>=1 and nums[i]<=n and nums[nums[i]-1] != nums[i]:
                tmp = nums[nums[i]-1]
                nums[nums[i]-1] = nums[i]
                nums[i] = tmp
            else:
                i+=1

        for i in range(n):
            if nums[i] != i+1:
                return i+1
        return n+1