41. First Missing Positive
41. First Missing Positive
题目
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. 丢失的数字](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)