# leetcode: First Missing Positive

#### Problem Description:

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.

####
Solution and **Precautions**:

Linear time usually requires hash table to do search in constant time, constant space requires we use a fixed number of variables or we directly use the input memory. Here constant space means the second case. So basically we use the input array A[] as our hash table, and by one pass through the whole array, we put each number a >= 1 and a <= n into the right position, that is a should be in position a-1, the key observation is that, the first missing positive could only be 1,….n, n+1, so basically we try to set all these positions in A to contain the right number, after this is done, we check the first slot where the position does not contain the right number, this position + 1 is the first missing positive. We can use swap or something else to do the thing that we set the position to contain the right number.

#### Tips and Divergent thinking:

N/A

**（全文完，原创文章，转载时请注明作者和出处）**

**（转载本站文章请注明作者和出处 烟客旅人 sigmainfy — http://www.sigmainfy.com，请勿用于任何商业用途）**