# Question

Formatted question description: https://leetcode.ca/all/41.html

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.

@tag-array



# Algorithm

Put 1 in the first position nums[0] of the array and 2 in the second position nums[1], that is, you need to put nums[i] on nums[nums[i]-1] to traverse the entire array,

• If nums[i] != i + 1, and nums[i] is an integer and is not greater than n, and nums[i] is not equal to nums[nums[i]-1], swap the two positions,
• if not satisfied above conditions are skipped directly, and the array is traversed again. If the number at the corresponding position is incorrect, the correct number will be returned.

### Note

The key is to deal with the collision. If there are repeated numbers 1, 1, or 2, 2. If the collision means that there is the correct number at the correct position, ++ will go to the next one.

Java