41. 缺失的第一个正数

🔴   🔖  数组 哈希表  🔗 力扣 LeetCode

题目

Given an unsorted integer array nums, return the smallest missing positive integer.

You must implement an algorithm that runs in O(n) time and uses O(1) auxiliary space.

Example 1:

Input: nums = [1,2,0]

Output: 3

Explanation: The numbers in the range [1,2] are all in the array.

Example 2:

Input: nums = [3,4,-1,1]

Output: 2

Explanation: 1 is in the array but 2 is missing.

Example 3:

Input: nums = [7,8,9,11,12]

Output: 1

Explanation: The smallest positive integer 1 is missing.

Constraints:

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

题目大意

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

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

解题思路

思路一：哈希表

为了减少时间复杂度，可以把 input 数组都装到 map 中，然后 i 循环从 1 开始，依次比对 map 中是否存在 i，只要不存在 i 就立即返回结果，即所求。但是这种方法的空间复杂度为 O(n)，不满足题意。

复杂度分析

• 时间复杂度：O(n)，需要遍历数组。
• 空间复杂度：O(n)，需要一个大小为 n 的哈希表存储数据。

---

思路二：原地哈希

原地哈希的意思是利用数组的索引来存储元素的存在性。具体来说，将每个值 x 放到数组的索引 x-1 处（即 nums[x-1]），如果 x 的值在 [1, n] 范围内。这样做的前提是，数组中只有正整数。

• 遍历数组：

  • 首先遍历数组，将每个有效的正整数放到正确的位置（即将 x 放到 nums[x-1]）。
  • 对于每个值 x，如果 1 ≤ x ≤ n，并且 nums[x-1] 不是 x，则交换 nums[i] 和 nums[x-1]，直到 nums[i] 在正确的位置。

• 第二次遍历：

  • 再次遍历数组，找到第一个位置 i，使得 nums[i] 不等于 i + 1，那么 i + 1 就是缺失的正整数。

• 边界情况：

  • 如果所有位置都满足 nums[i] = i + 1，那么缺失的第一个正整数就是 n + 1。

复杂度分析

• 时间复杂度：O(n)，数组只遍历了两次。
• 空间复杂度：O(1)，只使用了常量级别的额外空间。

代码

哈希表

/**
 * @param {number[]} nums
 * @return {number}
 */
var firstMissingPositive = function (nums) {
	let map = new Map();
	for (let i of nums) {
		map.set(i, true);
	}
	let i = 1;
	while (true) {
		if (map.has(i)) i++;
		else return i;
	}
};

原地哈希

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

	// 1. 将每个数放到对应的位置
	for (let i = 0; i < n; i++) {
		while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] !== nums[i]) {
			// 交换 nums[i] 和 nums[nums[i] - 1]
			const temp = nums[i];
			nums[i] = nums[temp - 1];
			nums[temp - 1] = temp;
		}
	}

	// 2. 查找第一个缺失的正整数
	for (let i = 0; i < n; i++) {
		if (nums[i] !== i + 1) {
			return i + 1; // 找到第一个缺失的正整数
		}
	}

	return n + 1; // 如果 1 到 n 的正整数都在
};

相关题目

题号	标题	题解	标签	难度
268	丢失的数字	[✓]	位运算 数组 哈希表 3+
287	寻找重复数	[✓]	位运算 数组 双指针 1+
448	找到所有数组中消失的数字		数组 哈希表
765	情侣牵手		贪心 深度优先搜索 广度优先搜索 2+
2336	无限集中的最小数字		设计 哈希表 有序集合 1+
2554	从一个范围内选择最多整数 I		贪心 数组 哈希表 2+
2557	从一个范围内选择最多整数 II 🔒		贪心 数组 二分查找 1+
2598	执行操作后的最大 MEX		贪心 数组 哈希表 1+
2996	大于等于顺序前缀和的最小缺失整数		数组 哈希表 排序