41.缺失的第一个正数

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

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

1. 利用鸽巢原理，遍历第一遍，如果当前位置的数不等于当前索引下标，则把这个数放到对应索引的位置nums[nums[i]]=nums[i]，不停的交换(如果发现nums[i]对应的坑位已经放了正确的数，那么说明nums[i]是重复的，直接置为-1)，直到当前位置的数越出数组范围或者当前位置填放了正确的数。

   第二次遍历如果从索引1开始，坑位正确，那么一直往后找直到nums[i]!=i即为答案。否则返回1。时间复杂度O(n)。

 public int firstMissingPositive(int[] nums) {
     if(nums.length==1)
     {
         if(nums[0]==1) return 2;
         else return 1;
     }
     for(int i=0;i<nums.length;i++)
     {
         if(nums[i]<0||nums[i]==i)
             continue;
         while(nums[i]>=0&&nums[i]<nums.length&&i!=nums[i]) //交换
         {
             if(nums[nums[i]]==nums[i])
                 nums[i]=-1;
             else
             {
                 int temp=nums[i];
                 nums[i]=nums[temp];
                 nums[temp]=temp;
             }
         }
     }
     if(nums[1]==nums[1])
     {
         int i=1;
         while(i<nums.length&&nums[i]==i) i++;
         if(nums[0]==nums.length&&i==nums.length) return nums.length+1;
         else return i;
     }   
     return 1;
  }