一刷。

这个题还是挺难的= =有一点需要利用的就是数组长度和数组里面数的值域关系。

数组长度是n，那么数字只可以是1-n。

做法是手动排序，把数字放到相应位置。

超出数组范围的>n or 0，不动。

可以放到相应位置的，放之前看看是不是有重复的，有点话不动= =；没有就和那个位置的元素互换位置。

最后遍历数组，和下标不符合规矩的就是缺失的。

都不缺失说明缺少n+1...

Time: O(n)

Space: O(1)

public class Solution {    public int firstMissingPositive(int[] nums) {        if (nums.length == 0) return 1;                int i = 0;        while (i < nums.length) {                        if (nums[i] <= 0 || nums[i] > nums.length) { // invalid cuz out of range                i ++;            } else if (nums[i] != nums[nums[i] - 1]) {  // swap to where it should be..if no duplicates                swap(nums, i, nums[i] - 1);            } else {                                    // duplicates= =                i ++;            }                    }                for (int j = 0; j < nums.length; j++) {            if (nums[j] != j + 1) {                return j + 1;            }        }        return nums.length + 1;    }        public void swap(int[] nums, int a, int b) {        int temp = nums[a];        nums[a] = nums[b];        nums[b] = temp;    }}