41. First Missing Positive

[Tcdian]

41. First Missing Positive

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

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

• 你的算法的时间复杂度应为O(n)，并且只能使用常数级别的额外空间。

[Tcdian]

Solution

• JavaScript Solution

/**
 * @param {number[]} nums
 * @return {number}
 */
var firstMissingPositive = function(nums) {
    for (let i = 0; i < nums.length; i++) {
        while (nums[i] > 0 && nums[i] <= nums.length && nums[nums[i] - 1] !== nums[i]) {
            swap(nums[i] - 1, i);
        }
    }
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] !== i + 1) {
            return i + 1;
        }
    }
    return nums.length + 1;

    function swap(x, y) {
        const temp = nums[x];
        nums[x] = nums[y];
        nums[y] = temp;
    }
};

• TypeScript Solution

function firstMissingPositive(nums: number[]): number {
    for (let i = 0; i < nums.length; i++) {
        while (nums[i] > 0 && nums[i] <= nums.length && nums[nums[i] - 1] !== nums[i]) {
            swap(nums[i] - 1, i);
        }
    }
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] !== i + 1) {
            return i + 1;
        }
    }
    return nums.length + 1;

    function swap(x: number, y: number) {
        const temp = nums[x];
        nums[x] = nums[y];
        nums[y] = temp;
    }
};