思路一： O(n)时间复杂度， O(n)空间复杂度。这是我自己思路，利用set。因为数组中重复的数和小于等于0的数都是没用的。那么我们只需要将大于0的数放进set中。接着我们数一下set中有几个数字，假设有5个数字，那么我们就该从1check到5，看set中有没有，没有的话就直接返回就行，就是最后的答案，如果都有的话那就返回6（5+1）。不难想，直接上代码：
class Solution { public int firstMissingPositive(int[] nums) { Set<Integer> set = new HashSet<>(); for(int num : nums){ if(num > 0){ set.add(num); } } int size = set.size(); for(int i = 1; i <= size; ++i){ if(!set.contains(i)){ return i; } } return size + 1; } }**思路二：**这也是lc的解答，这个时间复杂度还是O(n)，但是空间复杂度是O(1)，不需要额外存储空间。他巧妙的用正负号来表示数字是否出现过，感觉挺难讲清楚的，是一个比较巧妙的方法，不过我并不expect我在面试中可以想到这种方法，所以就当了解一下就好了，具体思路可以看了lc解答，看完了就发现也挺简单的，就是太巧妙了，很难想到。下面直接上代码：
class Solution { public int firstMissingPositive(int[] nums) { int len = nums.length; // 判断数组中是否有1，因为后面要将一些数替换成1，所以这步必须有 boolean flag = false; for(int num : nums){ if(num == 1){ flag = true; break; } } if(flag == false){ return 1; } // 替换成1 for(int i = 0; i < len; ++i){ if(nums[i] <= 0 || nums[i] > len){ nums[i] = 1; } } // traverse数组，通过改变符号来表明数字（下标）是否出现过，这边很巧妙的利用了下标。负号代表出现过。 for(int i = 0; i < len; ++i){ int a = Math.abs(nums[i]); if(a == len){ nums[0] = -Math.abs(nums[0]); }else{ nums[a] = -Math.abs(nums[a]); } } // 返回第一个是正数的下标，就是答案 for(int i = 1; i < len; ++i){ if(nums[i] > 0){ return i; } } // 下标0用来标记数字len是否出现过的，len为可能的最大的正数 if(nums[0] > 0){ return len; } // 数组包含从1开始到len的所有正数，那么就不存在missing了，所以返回len + 1 return len + 1; } }总结： 无
