41. First Missing Positive

🔴   🔖  数组 哈希表  🔗 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

题目大意

找到缺失的第一个正整数。

解题思路

为了减少时间复杂度，可以把 input 数组都装到 map 中，然后 i 循环从 1 开始，依次比对 map 中是否存在 i，只要不存在 i 就立即返回结果，即所求。

代码

/**
 * @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. 丢失的数字
• 287. 寻找重复数
• 448. 找到所有数组中消失的数字
• 765. 情侣牵手
• 2336. 无限集中的最小数字
• 2554. 从一个范围内选择最多整数 I
• 2598. 执行操作后的最大 MEX
• 🔒 Maximum Number of Integers to Choose From a Range II

- [268. 丢失的数字](https://leetcode.com/problems/missing-number)
- [287. 寻找重复数](https://leetcode.com/problems/find-the-duplicate-number)
- [448. 找到所有数组中消失的数字](https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array)
- [765. 情侣牵手](https://leetcode.com/problems/couples-holding-hands)
- [2336. 无限集中的最小数字](https://leetcode.com/problems/smallest-number-in-infinite-set)
- [2554. 从一个范围内选择最多整数 I](https://leetcode.com/problems/maximum-number-of-integers-to-choose-from-a-range-i)
- [2598. 执行操作后的最大 MEX](https://leetcode.com/problems/smallest-missing-non-negative-integer-after-operations)
- [🔒 Maximum Number of Integers to Choose From a Range II](https://leetcode.com/problems/maximum-number-of-integers-to-choose-from-a-range-ii)