First Missing Positive
Problem
Given an unsorted integer array, find the first missing positive integer.
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.
Solution
The most straightforward solution is to sort the array, but the time complexity would be O(n log n)
.
Solution 1
Assume the array length is n
, any positive number i
equal or less than n
can be placed in the array at i - 1
, so if we check each number num[i]
in the array, if 0 < num[i] <= n
, we keep swapping the number to it's position, otherwise we ignore this out-of-range number. Then from the beginning, find that first i
that num[i] != i + 1
.
(Check the Java solution below.)
Solution 2
First convert all non-positive numbers to n + 1
so that they are still out-of-range, but all the numbers in the array are positive now, and we can use the sign of the number to denote whether the number exists.
Then for each num[i]
, if it is within range (0 < num[i] <= n
), then set num[num[i] - 1]
to negaive. After that, if num[k]
is negative, k
must have appeared in the values of the array, so we can simply return k + 1
(k
is the index, starting from 0
) of the first positive num[k]
we meet. If we cannot find such k
, all positive numbers are in the array, so return n + 1
instead.
(Check the Go solution below.)
Language Specific Notes
Go
There's no Abs()
function for int
(only for float64
). You need to handle the absolute numbers on your own.