41. First Missing Positive

Given an unsorted integer array, find the smallest missing positive integer.
Example 1:Input: [1,2,0]Output: 3
Example 2:Input: [3,4,-1,1]Output: 2
Example 3:Input: [7,8,9,11,12]Output: 1
Note:Your algorithm should run in O(n) time and uses constant extra space.
难度：hard
题目：给定一无排序的整数数组，找出丢失的最小正整数。
注意：算法时间复杂度为 O(n) 空间复杂度为常量。
思路：清除所有原数组中不在范围[1,n(数组长度)] 的值。并将所有 index + 1 = nums[index] 的数组归位。归位过程中相等的两个元素不用交换（避免无限循环）
Runtime: 5 ms, faster than 100.00% of Java online submissions for First Missing Positive.
class Solution {
public int firstMissingPositive(int[] nums) {
if (null == nums || nums.length < 1) {
return 1;
}

int t = 0, n = nums.length;
for (int i = 0; i < n; i++) {
// make it as zero to avoid array index overflow
if (nums[i] <= 0 || nums[i] > n) {
nums[i] = 0;
} else if ((i + 1) != nums[i] && nums[nums[i] – 1] != nums[i]) {
t = nums[nums[i] – 1];
nums[nums[i] – 1] = nums[i];
nums[i–] = t;
}
}

for (int i = 0; i < nums.length; i++) {
if ((i + 1) != nums[i]) {
return i + 1;
}
}

return n + 1;
}
}