乘风破浪：LeetCode真题_041_First Missing Positive
一、前言
这次的题目之所以说是难，其实还是在于对于某些空间和时间的限制。
二、First Missing Positive
2.1 问题
2.2 分析与解决
读了题目我们或许还不理解题意，其实是说正常的数组应该是[1,2,3,4....]这样的数组，或者打乱次序的，但是对于不是这样的数组，我们需要从中找到从那个数字开始缺少的，这个数字就是最小的数字，比如2,3,4，那么缺少的就是1。比如1,2,4，就是少了3。这样我们就理解了。但是时间复杂度要求O(n)，空间使用是常数级别的。
我们仔细思考一下，其实下标和这个是有关系的，正常的，最终都可以变成num[i]=i+1，于是我们可以将数组进行一边扫描，如果已经满足这种性质的不用动，如果num[i]的值小于1或者大于长度的都是不应该存在的，因此置为一个标志，便于以后报错。如果在范围之内的，我们就让它们物归原位。比如num[i]=x,那么这个元素应该在下标为x-1的位置上，因此我们将num[x-1]和num[i]上的元素进行交换。交换的时候如果发现这两个值相等，则将非本位的值置为零，否者直接交换。
class Solution {
// let's rearrange the numbers in the array between 1 and length
// in order (in place), leaving a 0 for numbers not present,
// and ignoring the numbers out of this range.
// then in second pass find the first zero occurence, or if none,
// return length+1
// for example, [3,4,-1,1] will become [1,0,3,4]
public int firstMissingPositive(int[] nums) {
for (int i=0; i<nums.length;) {
int n = nums[i];
if (n<1 || n>nums.length) {
nums[i]=0; // out of range, remove
i++;
} else if (n-1==i) {
i++; // in range and in position, leave as is
} else {
// in range but not in position, swap
int temp = nums[n-1];
nums[n-1]=n;
nums[i]=(temp==n)?0:temp;//这里最妙的就是没有i++，以此确保下一次还从这个地方开始
}
}
for (int i=0; i<nums.length; i++) {
if (nums[i]==0)
return i+1;
}
return nums.length+1;
}
}
三、总结
遇到问题需要和实际的条件相联系，另外需要认真的判断所有的可能。