思路 索引作为哈希表。

数据预处理

就地算法

整体算法

code

  public int firstMissingPositive(int[] nums) {
        int n = nums.length;
    int contain1 = 0;
    //判断是否出现了1
    for(int i:nums){
        if(i==1){
          contain1++;
        break;
      }
    }
    //如果没有出现1 则最小正整数是1
    if(contain1==0)
      return 1;
    //如果出现了1且只有1 则返回2
    if(n==1)
      return 2;
    //将负数 0 大于n的数替换为1
    for(int i=0;i<n;i++){
      if(nums[i]<=0||nums[i]>n)
        nums[i]=1;
     // 使用索引和数字符号作为检查器
    // 例如，如果 nums[1] 是负数表示在数组中出现了数字 `1`
    // 如果 nums[2] 是正数 表示数字 2 没有出现 
    for(int i=0;i<n;i++){
       int a = Math.abs(nums[i]);
      if(a==n)            //使用0索引来存储数字n有没有出现过
        nums[0]=-Math.abs(nums[0]);
      else        //如果出现过 将对应的位置更新为负数
        nums[a]=-Math.abs(nums[a]);
    }
      //从第1个元素开始 找第一个不是负数的索引下标
    for(int i=1;i<n;i++)
      if(nums[i]>0)
        return i;
      //判断n有没有出现过
     if(nums[0]>0)
       return n;
      //如果都出现过 则返回n+1
      return n+1;
  }