# First Missing Positive

Given an **unsorted** integer array, find the first **missing** positive integer.Have you met this question in a real interview?  Yes

#### 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.

既然不能建立新的数组，那么我们只能覆盖原有数组，我们的思路是把1放在数组第一个位置nums\[0]，2放在第二个位置nums\[1]，即需要把nums\[i]放在nums\[nums\[i] - 1]上，那么我们遍历整个数组，如果nums\[i] != i + 1, 而nums\[i]为整数且不大于n，另外nums\[i]不等于nums\[nums\[i] - 1]的话，我们将两者位置调换，如果不满足上述条件直接跳过，最后我们再遍历一遍数组，如果对应位置上的数不正确则返回正确的数，代码如下：

```java
public class Solution {
    /**
     * @param A: An array of integers
     * @return: An integer
     */
    public int firstMissingPositive(int[] A) {
        // write your code here
        if(A == null || A.length == 0){
            return 1;
        } 
        
        for (int i =0; i < A.length ;++i ){
            while(A[i] > 0 && A[i] <= A.length && A[i] != i+1){
                int tmp = A[A[i]-1];
                if(tmp == A[i]){
                    break;
                }
                
                A[A[i]-1] = A[i];
                A[i] = tmp;
            }
            
        } 
        
        for(int i = 0; i < A.length; i++){
            if(A[i] != i+1){
                return i+1;
            }
        }
        
        return A.length + 1;
    }
}
```

好理解的解法

time o(n),space o(1)

{% embed url="https://www.youtube.com/watch?v=jfb72FfxWKU" %}

```java
class Solution {
    public int firstMissingPositive(int[] nums) {
        if(nums == null || nums.length == 0)
            return 1;
        
        for(int i = 0; i < nums.length; i++){
            while(nums[i] > 0 && nums[i] <= nums.length && nums[nums[i]-1] != nums[i]){
                int tmp = nums[nums[i] - 1];
                nums[nums[i] -1] = nums[i];
                nums[i] = tmp;
            }
        }
        
        for(int i = 0; i < nums.length;i++){
            if(nums[i] != i+1){
                return i+1;
            }
        }
        
        return nums.length+1;
    }
}
```
