缺失的第一个正数

来源Leetcode第41题缺失的第一个正数

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

示例 2:

输入: [3,4,-1,1]
输出: 2

Method 1

emmm，这题做的时候思路混乱了，而且这题的题解很怪，先看官方的题解吧。

来自题解的算法：

算法

• 检查 1 是否存在于数组中。如果没有，则已经完成，1 即为答案。
• 如果 nums = [1]，答案即为 2 。
• 将负数，零，和大于 n(定义 n 为数组nums的长度) 的数替换为 1 。
• 遍历数组。当读到数字 a 时，替换第 a 个元素的符号。
• 注意重复元素：只能改变一次符号。由于没有下标 n ，使用下标 0 的元素保存是否存在数字 n。
• 再次遍历数组。返回第一个正数元素的下标。
• 如果 nums[0] > 0，则返回 n 。
• 如果之前的步骤中没有发现 nums 中有正数元素，则返回n + 1。

总的来说，就是用数组自身来检查所求的最小正数。

代码如下：

class Solution {
  public int firstMissingPositive(int[] nums) {
    int n = nums.length;

    // 基本情况
    int contains = 0;
    for (int i = 0; i < n; i++)
      if (nums[i] == 1) {
        contains++;
        break;
      }

    if (contains == 0)
      return 1;

    // nums = [1]
    if (n == 1)
      return 2;

    // 用 1 替换负数，0，
    // 和大于 n 的数
    // 在转换以后，nums 只会包含
    // 正数
    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]);
      // 如果发现了一个数字 a - 改变第 a 个元素的符号
      // 注意重复元素只需操作一次
      if (a == n)
        nums[0] = - Math.abs(nums[0]);
      else
        nums[a] = - Math.abs(nums[a]);
    }

    // 现在第一个正数的下标
    // 就是第一个缺失的数
    for (int i = 1; i < n; i++) {
      if (nums[i] > 0)
        return i;
    }

    if (nums[0] > 0)
      return n;

    return n + 1;
  }
  
}

桶排序

让我们来看另一个解法：利用桶排序
同样是利用数组自身作为一个索引表，在做这道题的时候，我们可以明确一个事实：

• 所要找的最小正数在1 - nums.length 之间
• 否则所要找的最小正数是nums.length + 1

利用这两个事实，我们可以将数组里的正数nums[i] 放在num[nums[i] - 1] 的位置上
之后遍历数组，如果nums[i] != i + 1,返回 i + 1 即可
否则返回 nums.length + 1

代码如下：

public class Solution {

    public int firstMissingPositive(int[] nums) {
        int len = nums.length;

        for (int i = 0; i < len; i++) {
            while (nums[i] > 0 && nums[i] <= len && nums[nums[i] - 1] != nums[i]) {
                // 满足在指定范围内、并且没有放在正确的位置上，才交换
                // 例如：数值 3 应该放在索引 2 的位置上
                swap(nums, nums[i] - 1, i);
            }
        }

        // [1, -1, 3, 4]
        for (int i = 0; i < len; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        // 都正确则返回数组长度 + 1
        return len + 1;
    }

    private void swap(int[] nums, int index1, int index2) {
        if (index1 == index2) {
            return;
        }
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}