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

提示：

• 1 <= nums.length <= $5 * 10^5$
• $-2^{31}$ <= nums[i] <= $2^{31} - 1$

解析

原地哈希：将每个正数 x 放到下标 x-1 的位置上，然后遍历找到第一个 nums[i] !== i+1 的位置。

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

  // 将每个数放到正确的位置：nums[i] 应该等于 i+1
  for (let i = 0; i < n; i++) {
    while (
      nums[i] > 0 &&
      nums[i] <= n &&
      nums[nums[i] - 1] !== nums[i]
    ) {
      // 交换 nums[i] 到正确位置
      const idx = nums[i] - 1;
      [nums[i], nums[idx]] = [nums[idx], nums[i]];
    }
  }

  // 找到第一个不在正确位置的数
  for (let i = 0; i < n; i++) {
    if (nums[i] !== i + 1) return i + 1;
  }
  return n + 1;
};

原地哈希的巧妙之处：利用数组本身作为哈希表，将值为 x 的元素交换到下标 x-1 处，从而实现 O(1) 空间。时间复杂度 O(n)。