Given an unsorted integer array, find the first missing positive integer.
For example,
Given[1,2,0]return3,
and[3,4,-1,1]return2.
Your algorithm should run in O(n) time and uses constant space.
https://oj.leetcode.com/problems/first-missing-positive/
思路：交换数组元素，使得数组中第i位存放数值(i+1)。最后遍历数组，寻找第一个不符合此要求的元素，返回其下标。整个过程需要遍历两次数组，复杂度为O(n)。
public class Solution {
public int firstMissingPositive(int[] A) {
if (A == null && A.length == 0)
return 1;
int n = A.length;
int i;
for (i = 0; i < n; i++) {
while (A[i] > 0 && A[i] != i + 1 && A[i] <= n
&& A[i] != A[A[i] - 1]) {
swap(A, i, A[i] - 1);
}
}
for (i = 0; i < n; i++)
if (A[i] != i + 1)
return i + 1;
return n + 1;
}
private void swap(int[] a, int i, int j) {
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
public static void main(String[] args) {
System.out.println(new Solution().firstMissingPositive(new int[] { 1,
2, 0 }));
System.out.println(new Solution().firstMissingPositive(new int[] { 3,
4, -1, 1 }));
System.out
.println(new Solution().firstMissingPositive(new int[] { 0 }));
System.out
.println(new Solution().firstMissingPositive(new int[] { 1 }));
System.out
.println(new Solution().firstMissingPositive(new int[] { 2 }));
System.out.println(new Solution()
.firstMissingPositive(new int[] { 0, 1 }));
System.out.println(new Solution()
.firstMissingPositive(new int[] { 1, 1 }));
}
}
[leetcode] First Missing Positive,布布扣,bubuko.com
[leetcode] First Missing Positive
原文：http://www.cnblogs.com/jdflyfly/p/3810750.html