给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

输入：nums = [1,2,0]
输出：3

 尝试的路途是痛苦的，不断的尝试新方法，错何尝不是一种乐趣

• 纯暴力（双层for循环）

 public int firstMissingPositive(int[] nums) {for (int i = 1; i <= nums.length; i++) {boolean has = false;for (int j = 0; j < nums.length; j++) {if (nums[j] == i) {has = true;break;}}if (!has) {//没有找到这个数，直接返回return i;}}return nums.length + 1;}

       第一层循环遍历[1,nums.length]的元素，第二层元素查看当前数组中是否存在，第一个不存在的就是第一个缺失的整数，这种纯暴力搜，案例肯定能过，但是时间复杂度过高，一般都会超时

• 排序+二分查找

       二分查找的时间复杂度是O(logn)的，这种一般是不会超时，但是我们要先将数组进行排序，因为二分查找的前提条件是具有单调性

 Arrays.sort(nums);

       遍历[1,nums.length]中的元素，通过二分搜索去在排序后的数组中查找，第一次没有查到就是第一个缺失的整数

for(int i=1;i<=nums.length;i++){int res=binarySearch(nums,i);if(res==-1){return i;}}

 普通的二分搜索：

public int binarySearch(int[] nums,int target){int left=0;int right=nums.length-1;while(left<=right){int mid=left+(right-left)/2;if(nums[mid]==target){return mid;}else if(nums[mid]>target){right=mid-1;}else{left=mid+1;}}return -1;}

• 哈希表
         利用哈希表对原数组进行一个存储，遍历[1,nums.length]中的元素，如果在set中不存在，就是第一个缺少的整数
   

   public int firstMissingPositive(int[] nums) {int len = nums.length;Set<Integer> hashSet = new HashSet<>();for (int num : nums) {hashSet.add(num);}for (int i = 1; i <= len; i++) {if (!hashSet.contains(i))return i;}return len + 1;}

  

• 位图

       假设我们使用一个位图（bitmap）来表示集合，其中每一位代表一个元素是否存在于集合中。但是这种位图只适合集合数量不是太多的情况，显然这道题不满足这个条件

错误实例：

 public int firstMissingPositive(int[] nums) {int len = nums.length;int hash = 0;for (int num : nums) {if (num > 0&&num<=nums.length) {  // 忽略非正整数hash |= 1 << (num - 1);//将当前元素加入位图}}for (int i = 1; i <= len + 1; i++) {//判断当前元素是否存在于位图if ((hash & (1 << (i - 1))) == 0) {return i;}}return len + 1; }

 基本也能过个80%+，但是我们怎么才能巧妙的利用这种方式去解决这个问题呢？

public int firstMissingPositive(int[] nums) {public int firstMissingPositive(int[] nums) {int length = nums.length;int bit[] = new int[((length - 1)>>5) + 1];for (int i = 0; i < nums.length; i++) {int digit = nums[i];//数组必须在1到length之间才有效if (digit >= 1 && digit <= length) {int index = (digit - 1)>>5;//x%N  如果N是2的次数可以写成 x&(N-1)bit[index] |= (1 << ((digit - 1) & 31));}}//最后在执行一遍循环，查看对应位置的元素是否正确，如果不正确直接返回for (int i = 0; i < nums.length; i++) {if ((bit[i >>5] & (1 << (i & 31))) == 0)return i + 1;}return length + 1; }}

• 置换

置换顾名思义就是通过不断的交换将数组中的值和索引相对应

       通过的不断的置换，对应的位置与相对应的索引进行匹配完成，再遍历原数组，第一个数值和索引不匹配的就是第一个缺失的整数

 public int firstMissingPositive(int[] nums) {if(nums==null||nums.length==0){return 0;}//置换 值和索引相匹配for(int i=0;i<nums.length;i++){while(nums[i]>=1&&nums[i]<=nums.length&&nums[nums[i]-1]!=nums[i]){int temp=nums[nums[i]-1];nums[nums[i]-1]=nums[i];nums[i]=temp;}}for(int i=0;i<nums.length;i++){if(nums[i]!=i+1){return i+1;}}return nums.length+1;}

• 对应法

      我们可以把每个元素存放到对应的位置，比如1存放到数组的第一个位置，3存放到数组的第3个位置， 如果是非正数或者大于数组的长度的值，我们不做处理，最后在遍历一遍数组，如果位置不正确，说明这个位置没有这个数，我们就直接返回

 public int firstMissingPositive(int[] nums) {for (int i = 0; i < nums.length; i++) {//如果在指定的位置就不需要修改if (i + 1 == nums[i])continue;int x = nums[i];if (x >= 1 && x <= nums.length && x != nums[x - 1]) {swap(nums, i, x - 1);i--;//抵消上面的i++，如果交换之后就不++；}}//最后在执行一遍循环，查看对应位置的元素是否正确，如果不正确直接返回for (int i = 0; i < nums.length; i++) {if (i + 1 != nums[i])return i + 1;}return nums.length + 1;}//交换两个数的值public void swap(int[] A, int i, int j) {if (i != j) {A[i] ^= A[j];A[j] ^= A[i];A[i] ^= A[j];}}

• 标记法

1. 因为数组中中按道理只允许出现[1,nums.length]的数字，所以我们首先可以先对数组中的元素进行处理，将大于等于数组长度和小于等于0的元素值改为nums.length+1(这里只要不是合理区间内的值都可以)
2. 遍历数组中的每一个元素，加假如遍历到3，因为数组中的索引是从0开始的，所以我们要把索引为2的值变为负数（负数相当于一个标志，如果一个索引的值为负数，证明该数已经出现过），如果相同的数岂不是给一个数加负号两次，负负得正，就相当于没有出现，所以我们为了避免这种情况，每次取负数的时候，都将原数字取绝对值以后再进行取反
3. 遍历修改后的数字，碰到第一个非负数，该数对应的索引+1就是我们缺失的第一个正数（正数说明没有其值进行标记）

public int firstMissingPositive(int[] nums) {//对入参进行判断if(nums==null||nums.length==0){return 0;}//将数组中大于数组长度的和小于等于零的值进行替换for(int i=0;i<nums.length;i++){if(nums[i]<=0||nums[i]>nums.length+1){nums[i]=nums.length+1;}}//遍历每一个元素，进行映射，符号代表该索引的整数已经出现过for(int i=0;i<nums.length;i++){int num=Math.abs(nums[i]);if(num<=nums.length){nums[num-1]=-Math.abs(nums[num-1]);}
}for(int i=0;i<nums.length;i++){if(nums[i]>0){return i+1;}}return nums.length+1;}