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.
一刷
题解：
找到第一个missing positive，要求O(n)。首先就想到了像sort colors一样的swap方法。把invalid case都swap到array的后部，两次pass就可以找到first mission positive。
Time Complexity - O(n)， Space Complexity - O(1)
二刷依然写得比较复杂， reference里面有很多很简洁的写法，要加以学习。思路是利用排除法和双指针夹逼，使用类似于sort colors里面的swap()来在O(n)的时间和O(1)的space遍历数组，我们有一下几种case:
- 当 nums == null || nums.length == 0的时候，我们返回最小正整数 1
- 设定lo = 0， hi = nums.length - 1
- 当nums[lo] <= 0或者nums[lo] > hi的时候，这两种情况为invalid，我们肯定能在数组中找到更合适的元素，我们swap(nums, lo, hi)，然后hi--
- 接下来，当nums[lo] = lo + 1的时候，这时候是valid condition，我们增加lo = lo + 1
- 假如nums[lo] < lo +1，经历过上面的条件以后，我们可以肯定nums[lo] - 1 >= 0并且nums[lo] - 1 < lo，说明我们之前已经处理过nums[lo] - 1这个index，并且找到了一个合理的值。那么现在我们可以判断出这里的nums[lo]是一个duplicate，我们执行 swap(nums, lo, hi--)把它移动到数组末尾去。这个条件说明在lo这个index出现了duplicate。
- 现在剩下的情况是我们的nums[lo] > lo + 1，并且nums[lo] < hi。这时候算是我们的一般情况，我们要把这个nums[lo]交换到他应该处于的为止，并且这个位置的index > lo而且index < hi。 因为在理想的情况下，我们的index与值的对应关系应该是i = nums[i] - 1，所以我们要尝试把nums[lo]换到nums[lo] - 1这个位置。但在这个时候我们需要进行一个判断， 就是假如 lo = 2， nums[lo] = 5， 假设nums[nums[lo] - 1] = nums[4]也等于5怎么办? 假如我们交换的话，那程序就会陷入死循环。这个时候我们判断出这里当前的nums[lo]其实也是一个duplicate，是higher index ”nums[lo] - 1"这个位置的duplicate。所以我们依然执行swap(nums, lo, hi--)，把这个数字交换到当前的尾部去。
- 最后的情况就是nums[lo] != nums[nums[lo] - 1]， 我们可以放心大胆地执行swap(nums, lo, nums[lo] - 1)，让循环去判断接下来的情况。
- 最后我们需要从头算一遍i从0到nums.length - 1， nums[i]是否等于 i + 1，假如不等，即可返回i+1，否则我们要返回nums.length + 1。
public class Solution {
public int firstMissingPositive(int[] nums) {
if(nums == null || nums.length == 0) return 1;
int lo = 0, hi = nums.length -1;
while(lo<=hi){
if(nums[lo] <= 0 || nums[lo] > hi) swap(nums, lo, hi--);
else if(nums[lo] == lo+1) lo++;
else if(nums[lo] < lo+1) swap(nums, lo, hi--);
else if(nums[lo] == nums[nums[lo] - 1]) swap(nums, lo, hi--);
else swap(nums, lo, nums[lo]-1);
}
for(int i=0; i<nums.length; i++){
if(nums[i]!=i+1) return i+1;
}
return nums.length+1;
}
private void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
