问题描述
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.
解决思路
假设数组长度为n，1. 交换：如果当前元素是1-n之间的数，则将其交换到合适的位置上（如果该位置不是该元素）；
2. 扫描 + 检查。
时间复杂度为O(n)，空间复杂度为O(1).
程序
public class Solution {
public int firstMissingPositive(int[] nums) {
if (nums == null || nums.length == 0) {
return 1;
}
int n = nums.length;
// swap
for (int i = 0; i < n; i++) {
int elem = nums[i];
if (elem < 1 || elem > n || elem == i + 1 || elem == nums[elem - 1]) {
continue;
}
swap(nums, i, elem - 1);
--i;
}
// scan and check miss
for (int i = 0; i < n; i++) {
if (nums[i] != i + 1) {
return i + 1;
}
}
return n + 1;
}
private void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
原文：http://www.cnblogs.com/harrygogo/p/4714770.html