```
/*
solution is very simple, make input nums to be [3,4,-1,1] as example:
1.Create an array the same length as input: [0,0,0,0]
2.From the start to the end, check if the element is a positive number.
3.Then change the created array according to step 2.
4.Check the array.
For example:
(Step 2) The first element of the input is 3, then
(Step 3) Change the 3rd element of array from 0 to 1. So the array from [0,0,0,0] to [0,0,1,0]
At the end the array should be: [1,0,1,1]
(Step 4) if there is still 0 left in the array. then the number of that element will be the answer.
In this case the answer is 2.
PS. There is the case like: [1,2,3,4] where the created array will become [1,1,1,1] at the end.
Then we should return length of array plus one, which is 5 here.
*/
public class Solution {
public int firstMissingPositive(int[] nums) {
int length = nums.length;
//return 1 if the input is an empty array
if(length == 0) return 1;
int[] list = new int[length];
//step 2 and 3: change the array accroding to nums[]
for(int i=0; i<length; i++){
//step 2: check if is positive
if(nums[i]>0 && nums[i]<=length){
//step 3: change the array
list[nums[i]-1] = 1;
}
}
//step 4: check if there is 0 left
for(int i=0; i<length; i++){
if(list[i] == 0){
//return the number of this 0
return i+1;
}
}
//case [1,2,3,4,...,length]
return length+1;
}
}
```