First Missing Positive

Question

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.

Tags

• Array

Thought

Since we are required to solve this problem in O(n) time and constant space, we cannot use sorting or hashing. Considering that in the problem Find All Numbers Disappeared in an Array, we use index to represent the integer we are searching, we can use the same idea here.

1. Change the value of zero and negative integers to n + 2 because this change will not affect the searching result.
2. In the loop for the array, if the integer n is not larger than n, use the integer n-1 as the index and change the value of the integer at n-1 to negative.

Code

class Solution(object):
    def firstMissingPositive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        # http://www.cnblogs.com/zuoyuan/p/3777496.html
        n=len(nums)
        for i in range(n):
            if nums[i]<=0: 
                nums[i]=n+2
        for i in range(n):
            if abs(nums[i])<=n:
                curr=abs(nums[i])-1
                nums[curr]=-abs(nums[curr])
        for i in range(n):
            if nums[i]>0: return i+1
        return n+1