41. First Missing Positive

Posted on

Desription

Given an unsorted integer array, find the smallest missing positive integer.

Example

Example 1:

Input: [1,2,0]
Output: 3
Example 2:

Input: [3,4,-1,1]
Output: 2
Example 3:

Input: [7,8,9,11,12]
Output: 1
Note:

Solution

用了map来做，空间换时间。不过这题的难度为什么是Hard。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * @param {number[]} nums
 * @return {number}
 */
var firstMissingPositive = function(nums) {
    let re = {};
    for (let i = 0; i < nums.length; i++){
        re[nums[i]] = 1;
    }
    
    for (let i=1; i <  Number.MAX_VALUE; i++){
        if (!re[i])
            return i;
    }
};