跳至主要內容

41. 缺失的第一个正数


41. 缺失的第一个正数

🔴   🔖  数组 哈希表  🔗 力扣open in new window LeetCodeopen in new window

题目

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;
	}
};

相关题目

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