41、缺失的第一个正数|算法（附思维导图+全部解法）300题

零标题：算法（leetode，附思维导图 + 全部解法）300题之（41）缺失的第一个正数

一题目描述

题目描述

二解法总览（思维导图）

思维导图

三全部解法

1 方案1

1)代码：

// 方案1 “无视要求，去重、排序、过滤 - 暴力法”

// 技巧：“有序胜过无序”。
// 通过sort方法（时间复杂度仅为 O(nlogn)）将无序的数组变有序是一件很划算的事情。

// 思路：
// 1）状态初始化。nums 去重、升序排列 并 只保留正整数部分
// 2）遍历 nums 
// 2.1）若 此时 nums[i] 和 resNum 不相等，则 退出循环 
// 2.2）否则 resNum++ 
// 3）返回结果 resNum 
var firstMissingPositive = function(nums) {
    // 1）状态初始化。nums 去重、升序排列 并 只保留正整数部分
    const l = nums.length;
    nums = [...new Set(nums)];
    nums = nums.sort((a, b) => a - b).filter(item => item > 0);
    let resNum = 1;

    // 2）遍历 nums 
    for (let i = 0; i < l; i++) {
        // 2.1）若 此时 nums[i] 和 resNum 不相等，则 退出循环 
        if (nums[i] !== resNum) {
            break;
        }
        // 2.2）否则 resNum++ 
        else {
            resNum++;
        }
    }

    // 3）返回结果 resNum 
    return resNum;
}

2 方案2

1)代码：

// 方案2 “无视题目要求 - 哈希法（JS里的 Map数据结构 ）”。
// 注：目前实现的 时间、空间复杂度都是 O(n)，不符合题目要求 —— “时间复杂度为 O(n) 并且只使用常数级别额外空间” 。

// 思路：
// 1）状态初始化：map = new Map(), resVal = 1 。
// 2）核心1：遍历 nums 。
// 2.1）若 当前 nums[i] 值大于0（即 为正整数），则 将其放入 map 中。
// 3）核心2：循环，只要此时 resVal 小于 l + 1（注：这里的边界是 l + ，例子：[1]）。
// 3.1）若 此时的resVal 不存在于 map 中，则 退出循环 。
// 3.2）若 此时的resVal 不存在于 map 中，则 退出循环 。
// 4）返回结果 resVal 。
var firstMissingPositive = function(nums) {
    // 1）状态初始化：map = new Map(), resVal = 1 。
    const l = nums.length;
    let map = new Map(),
        resVal = 1;

    // 2）核心1：遍历 nums 。
    for (let i = 0; i < l; i++) {
        // 2.1）若 当前 nums[i] 值大于0（即 为正整数），则 将其放入 map 中。
        const tempVal = nums[i];
        if (tempVal > 0) {
            // 注：这里的 1（可换任何值） 起标记作用、 无意义！
            map.set(tempVal, 1);
        }
    }

    // 3）核心2：循环，只要此时 resVal 小于 l + 1（注：这里的边界是 l + ，例子：[1]）。
    while (resVal < l + 1) {
        // 3.1）若 此时的resVal 不存在于 map 中，则 退出循环 。
        if (!map.has(resVal)) {
            break;
        }
        // 3.2）若 此时的resVal 不存在于 map 中，则 退出循环 。
        else {
            resVal++;
        }
    }

    // 4）返回结果 resVal 。
    return resVal;
}

3 方案3

1)代码：

// 方案3 “置换法”。
// 参考：
// 1）https://leetcode-cn.com/problems/first-missing-positive/solution/que-shi-de-di-yi-ge-zheng-shu-by-leetcode-solution/

// 思路：
// 1）状态初始化：resVal resVal = l + 1 。
// 2）遍历 nums 。
// 2.1）若 nums[i] 值在 范围 [0, l - 1] 且 nums[nums[i] - 1] 不等于 nums[i]，
// 则 不断（“需循环处理！！”）交换下标 nums[i] - 1 和 i 上的值。
// 3）遍历 nums 。
// 3.1）若 此时的 nums[i] 不等于 i + 1 ，则 resVal 置为 i + 1 并 退出循环处理。
// 4）返回结果 resVal 。
var firstMissingPositive = function(nums) {
    // 1）状态初始化：resVal resVal = l + 1 。
    const l = nums.length;
    let resVal = l + 1;

    // 2）遍历 nums 。
    for (let i = 0; i < l; i++) {
        // 2.1）若 nums[i] 值在 范围 [0, l - 1] 且 nums[nums[i] - 1] 不等于 nums[i]，
        // 则 不断（“需循环处理！！”）交换下标 nums[i] - 1 和 i 上的值。
        while (nums[i] > 0 && nums[i] <= l && nums[nums[i] - 1] !== nums[i]) {
            [nums[nums[i] - 1], nums[i]] = [nums[i], nums[nums[i] - 1]];
        }
    }

    // 3）遍历 nums 。
    for (let i = 0; i < l; i++) {
        // 3.1）若 此时的 nums[i] 不等于 i + 1 ，则 resVal 置为 i + 1 并 退出循环处理。
        if (nums[i] !== i + 1) {
            resVal = i + 1;
            break;
        }
    }

    // 4）返回结果 resVal 。
    return resVal;
}

四资源分享 & 更多

1 历史文章 - 总览

历史文章 - 总览

2 【资源分享】算法通关 + 面试宝典

1）算法通关40讲（极客 - 外企大佬讲的）：
链接: https://pan.baidu.com/s/1C175QEmcAunjnCzYzoLBz 提取码: hjna

2）动态规划专题（价值几百美刀~）：https://www.bilibili.com/video/BV1nt4y1Y7nz

3）前端面经：
3.1）https://www.nowcoder.com/tutorial/96
3.2）https://muyiy.cn/question
3.3）https://hub.fastgit.org/haizlin/fe-interview/blob/master/category/history.md

注：若失效请前往VX公众号： 码农三少 ，发送关键字： LeetCode 或 算法 ，即可获取最新的链接~