My code:
public class Solution {
public int firstMissingPositive(int[] nums) {
if (nums == null || nums.length == 0) {
return 1;
}
int i = 0;
while (i < nums.length) {
if (nums[i] <= 0 || nums[i] > nums.length || nums[i] == i + 1) {
i++;
continue;
}
else if (nums[nums[i] - 1] != nums[i]) {
int temp = nums[nums[i] - 1];
nums[nums[i] - 1] = nums[i];
nums[i] = temp;
}
else {
i++;
}
}
for (i = 0; i < nums.length; i++) {
if (nums[i] != i + 1) {
return i + 1;
}
}
return nums.length + 1;
}
}
reference:
https://discuss.leetcode.com/topic/10351/o-1-space-java-solution/2
他的思路很简单。就是把本该出现在某个位置的数字移动过去。如果这个数字<= 0 或者超过了数字的最大可能出现的数 nums.length,或者他该摆放的位置已经摆放了正确的数字，那就直接略去，i++
最后再从头扫描一遍数组，碰到第一个不对的就直接返回index + 1
做法很巧。仔细思考，里面有counting sort 的思想。
counting sort 归根结底，也是一种hash的思想 + 计数器
而这道题目，用到了这个 hash的思想。
是啊，hashtable 也是 数组。我一开始只能用时间O(n) 空间O(n)做出来。空间全部浪费在了构建哈希表上。忘记了，这个数组本身，也是一个hash table.同时记住，这种思想是有条件的。必须要有明确的范围。
Anyway, Good luck, Richardo! -- 09/01/2016
