41. 缺失的第一个正数

题目描述

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

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

示例 1：

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

输出：3

解释：范围 [1,2] 中的数字都在数组中。

示例 2：

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

输出：2

解释：1 在数组中，但 2 没有。

示例 3：

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

输出：1

解释：最小的正数 1 没有出现。

提示：

• 1 <= nums.length <= 105
• -231 <= nums[i] <= 231 - 1

出处：LeetCode

解法一：哈希表

思路

我们可以使用一个哈希表 map 来存储数组 nums 中的元素。接着，我们可以遍历 1 到 n 的所有正整数，找到第一个不在哈希表 map 中的正整数。

代码

function firstMissingPositive(nums: number[]): number {
  const n = nums.length;
  const map = new Map<number, boolean>();

  for (const num of nums) {
    map.set(num, true);
  }

  for (let i = 1; i <= n; i++) {
    if (!map.has(i)) {
      return i;
    }
  }

  return n + 1;
}

复杂度分析

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

解法二：原地哈希

思路

我们可以将数组 nums 中的元素放到正确的位置上，使得 nums[i] = i + 1。接着，我们可以遍历数组 nums，找到第一个不满足 nums[i] = i + 1 的元素。

代码

function firstMissingPositive(nums: number[]): number {
  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++) {
    if (nums[i] !== i + 1) {
      return i + 1;
    }
  }

  return n + 1;
}

复杂度分析

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$