[leetcode]First Missing Positive

关键是不要往复杂处想..
其实思路对的用hashtable,但是space是O(1)的话 就要采用给的array..
然后给的array 采用swap
把a[i] 放到 array[a[i]-1] 处... (array和a是一样的..) swap完后 要是得到的值不在range 或者下一次要swap的位置已经有正确的数了 就跳过...

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

public class Solution { public int firstMissingPositive(int[] nums) { if (nums == null || nums.length == 0) return 1; if (nums.length == 1) return nums[0] == 1?2:1; int i = 0; while (i < nums.length){ if (nums[i] >= 1 && nums[i] <= nums.length && nums[nums[i]-1] != nums[i]){ swap(nums, i, nums[i]-1); }else{ i++; } } for (int j = 0; j <nums.length; j++){ if (nums[j] != j+1) return j+1; } return nums.length+1; } private void swap(int[]nums, int index1, int index2){ int temp = nums[index1]; nums[index1] = nums[index2]; nums[index2] = temp; } }