从零学算法41

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

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

示例 1：

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

输出：3

示例 2：

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

输出：2

示例 3：

输入：nums = [7,8,9,11,12]

输出：1

• 我的想法很简单，当该数组排序并去重后，再去掉小于等于 0 的部分，最终遍历数组时，判断是否为从 1 开始连续的数，比如 [1,2,3] 那就返回最大值 + 1 即 4，若不为从 1 开始的连续的数组，比如 [1,3,4] 中，nums[0] == 1，但是 nums[1] != 2，说明缺失了 2，那就直接返回 2 即可。

•   public int firstMissingPositive(int[] nums) {  // 排序      Arrays.sort(nums);      int i = 0;      // 从大于 0 处开始遍历，相当于去除了小于等于 0 的部分      while(i      // 相当于去重          while(i      int n = nums.length;      for(int i = 0;i      // 首先数在理想数组范围      //  其次如果 nums[i] 上面的数如果不是 i+1 就把它换到正确的位置，继续判断换过来的数      // 直到 num[i] = i + 1 就结束这一轮循环          while((nums[i]0 && nums[i]               swap(nums,i,nums[i]-1);          }      }      for(int i = 0;i          if(nums[i]!=i+1)return i+1;      }      return n+1;  }  public void swap(int[] nums,int i,int j){      int temp = nums[i];      nums[i]=nums[j];      nums[j]=temp;  }