缺失的第一个正数

题目

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

提示:

• 1 <= nums.length <= 5 * 10⁵
• -2³¹ <= nums[i] <= 2³¹ - 1

示例

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

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

输入: nums = [7, 8, 9, 11, 12]
输出: 1

题解

这道题的思路是使用原地哈希, 即如果数组中包含 x ∈ [1, n], 那么恢复后, 数组的第 x - 1 个元素为 x.

以示例 nums = [3, 4, -1, 1] 为例, 它会通过一次操作, 被转化成 [1, -1, 3, 4]. 然后再来一次遍历, 发现 nums[1] 不是 2, 即找出了缺失的数字是 2.

那么我们如何将数组进行恢复呢? 我们可以对数组进行一次遍历, 如果对于遍历到的数 nums[i], 我们记为 x, 在 [1, n] 这个闭区间内, 但没有在 x - 1 的位置, 那我们就将 x 和 nums[x - 1] 进行交换.

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
var firstMissingPositive = function (nums) {
  const n = nums.length

  // 数组恢复
  for (let i = 0; i < n; i++) {
    while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] !== nums[i]) {
      ;[nums[nums[i] - 1], nums[i]] = [nums[i], nums[nums[i] - 1]]
    }
  }

  for (let i = 0; i < n; i++) {
    // 预期 nums[i] 要等于 i + 1, 如果不相等即为缺失的数字
    if (nums[i] !== i + 1) {
      return i + 1
    }
  }

  // 如果在数组中间不存在缺失的数字, 则返回数组长度 + 1
  return n + 1
}

Rust

pub fn first_missing_positive(nums: Vec<i32>) -> i32 {
    let mut nums = nums;
    let n = nums.len();

    for i in 0..n {
        while nums[i] > 0 && nums[i] <= (n as i32) && nums[(nums[i] - 1) as usize] != nums[i] {
            let j = (nums[i] - 1) as usize;
            nums.swap(i, j);
        }
    }

    for i in 0..n {
        if nums[i] != i as i32 + 1 {
            return i as i32 + 1;
        }
    }

    n as i32 + 1
}