41. First Missing Positive

Leetcode link

题目简介

/**
 * @param {number[]} nums
 * @return {number}
 */

题目给我们一个数字数组 nums，里面包含正数，负数，与 0

要求我们求出 nums 中没出现的最小正整数是多少

要求使用 O(n) 时间复杂度与 O(1) 空间复杂度

解题思路

这题最大的难点就是如何在题目要求的复杂度中得出解答

核心的解题思路就是，我们通过数组的下标位置标记在当前数组中出现了哪些正整数

一旦我们完成了标记，后面只需要一次遍历看哪个下标没有标记即可

解题步骤分为三步：

1. 清洗数组

遍历数组，筛选出不符合范围条件的数字：nums[i] <=0 || nums[i] > len（因为一个长度为 len 的数组最多有 1~len 总共 len 个正整数所以超出这个范围的我们不考虑）

我们将超出这个范围的数字赋值成 len+1

2. 标记位置

遍历数组，找出符合范围的数字，并且将该数字对应的下标值为负（标记）

3. 寻找位置

遍历数组，寻找第一个不为负的元素对应下标（元素为正代表没有出现过）

如果遍历完数组都为负，则返回 len+1

Javascript

/**
 * @param {number[]} nums
 * @return {number}
 */
var firstMissingPositive = function (nums) {
    const len = nums.length
    for (let i = 0; i < len; i++) {
        if (nums[i] <= 0 || nums[i] > len) {
            // use dummy number to replace original one which is out of range
            nums[i] = len + 1
        }
    }

    for (let i = 0; i < len; i++) {
        const idx = Math.abs(nums[i])
        if (idx <= len) {
            // we use idx and negative sign to mark the number in the range
            nums[idx - 1] = -Math.abs(nums[idx - 1])
        }
    }

    for (let i = 0; i < len; i++) {
        if (nums[i] > 0) {
            // we find the first number that is positive(positive means no appearance)
            return i + 1
        }
    }

    // if every number in range [1, len] shows up, we return len+1
    return len + 1
};