# 41. First Missing Positive

[ **41. First Missing Positive**](https://leetcode.com/problems/first-missing-positive/discuss/158092/Java-O\(1\)-time-and-O\(1\)-space-no-need-to-swap-just-play-with-the-sign-of-the-numbers)

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

**Example 1:**

```
Input: [1,2,0]
Output: 3
```

**Example 2:**

```
Input: [3,4,-1,1]
Output: 2
```

**Example 3:**

```
Input: [7,8,9,11,12]
Output: 1
```

**Note:**

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

***My Solutions：***

同268题，448题类似，可以用sort和hashset，但只有方法3：利用index满足 Time: O(n); Space: O(1)

方法3：用数组nums\[i]存放（i + 1），从头开始遍历数组，哪个数值没有放在正确的位置（忽略不符合要求的数），将这个数交换到正确的位置（比如对于数字1，数组上index =0的地方应该是1；对于数字2，数组上index=1的地方应该是2）。最后，再从i = 0 开始遍历数组，第一个nums\[i] != i + 1的i+1数即为缺失的数据。因为这个位置没有被放置正确过，说明数组中没有这个位置的对应数字。如果都扫完了却一个都没缺，返回数组长度+1（e.g. \[1,2] 返回3）

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

方法1：sort

Time: O(nlgn); Space: O(1)

```
class Solution {
    public int firstMissingPositive(int[] nums) {
        Arrays.sort(nums);
        int count = 1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] <= 0) continue;
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            if (nums[i] == count) {
                count++;
            } else {
                return count;
            }
        }
        return count;
    }
}
```

方法2：hashset

Time: O(n); Space: O(n)

```

public class Solution {
    public int firstMissingPositive(int[] A) {
        int miss = A.length + 1;
        
        HashSet<Integer> hashset = new HashSet<Integer>();
        for (int i = 0; i < A.length; i ++) {
            hashset.add(A[i]);
        }
        
        for (int i = 1; i <= A.length; i ++) {
            if (!hashset.contains(i)) {
                miss = i;
                break;
            }
        }
        return miss;
    }

```
