My code:
public class Solution {
public int firstMissingPositive(int[] nums) {
if (nums == null || nums.length == 0)
return 1;
/** change array. move elem to right locations.
*The first elem while break this rule is the first missing positive.
*/
for (int i = 0; i < nums.length; i++) {
while (nums[i] != i + 1) {
if (nums[i] <= 0 || nums[i] > nums.length) // if out of range, ignore. It should be in [1, n]
break;
else if (nums[i] == nums[nums[i] - 1]) // if the repeating elem in right location, ignore or it will cause // infinite loop
break;
else { // swap. nums[i] should come up in index of nums[i] - 1. And swap nums[nums[i] - 1] to nums[i] to // check again
int toIndex = nums[i] - 1;
nums[i] = nums[toIndex];
nums[toIndex] = toIndex + 1;
}
}
}
/** find the first elem which is not in the right location */
for (int i = 0; i < nums.length; i++) {
if (nums[i] != i + 1)
return i + 1;
}
return nums.length + 1;
}
}
这道题目还是挺有意思的。很有意思。
因为我不仅没有做出来，而且一开始代码都读不懂。然后昨天又浪费了一天看直播去了。。。。操
下来说说这道题目。他的题意说的也不是很清楚。不，需要理解清楚。
如果缺了1， 那么返回的就是1
如果1有了，缺了2，那么返回的就是2
如果1, 2都有了，缺了3，那么返回的就是3
以此类推。
。。。
当1, 2, ... n - 1 都有了， 缺了 n， 那么返回的就是 n
如果[1, n] 都有了，那么返回的就只能是 n + 1
我们关注的只是[1, n] 之间从哪里开始缺失了
所以我们要做这么一件事，把相应的元素移动到对应的位置上。
比如，
3, 4, -1, 1
首先判断， 3 不应该出现在index = 0 处
3 应该出现在 nums[2] 处，于是交换 nums[0] and nums[2]
-1, 4, 3, 1
判断，-1， <= 0, 不应该出现在该数列中，没地方可以放他。于是就放在这里。
判断4， 不应该出现在index = 1, 处。
4 应该出现在nums[3]处， 于是交换 nums[1] and nums[3]
-1, 1, 3, 4
判断1, 不应该出现在index = 1的位置，
应该出现在nums[0], 于是交换 nums[0] and nums[1]
1, -1, 3, 4
判断 -1, <= 0, 直接略去，转到下一种情况。
nums[2] = 3, right
nums[3] = 4 right
end loop
然后再进行一次遍历，找到那个第一个不符合规则的数，
规则为， nums[i] == i + 1
同时，还要考虑到一种情况，当我要move的位置已经有了正确元素，即这个重复的元素在正确的位置上时，我就直接停止该内层loop，否则会一直将两个一样的数不停地交换，而新的情况不会加入进来，导致死循环。
这道题木还是很经典的，以前也从来没有碰到过这样的思路的题目。
参考的链接：
http://www.programcreek.com/2014/05/leetcode-first-missing-positive-java/
http://blog.csdn.net/nanjunxiao/article/details/12973173
Anyway, Good luck, Richardo!
