Given an unsorted integer array, find the first missing positive integer.
For example,
Given
and
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.
At first I thought the problem means we need to find the first missing positive in a sequence of positive integers, turns out it literately means the first missing integer, like, 1, 2, 3, .., i - 1, i + 1, ... n we are missing i.Google tells me that we should refer to the Counting sort algorithm. Here is a link of a good of counting sort visualization.
The basic idea is sort all positive elements by swapping them so that they are in the order of A[i] = i + 1. The missing element must be in the current array, so any element that is larger than A.length or <= 0 is not taken into account.
Traverse the array again and return any element that is not in the correct order, i.e., A[i] != i + 1 or A.length + 1 if everything is in order.
public class MissingPositive { public int firstMissingPositive(int[] A) { if (A == null) throw new NullPointerException("Null array!"); if (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) { if (A[A[i] - 1] == A[i]) break; swap(A, i, A[i] - 1); } } for (int i = 0; i < A.length; i++) { if (A[i] != i + 1) return i + 1; } //if every element is in place, we are missing the next one! return A.length + 1; } private void swap(int[] A, int i, int j) { int tmp = A[i]; A[i] = A[j]; A[j] = tmp; } }
No comments:
Post a Comment