LeetCode 之 JavaScript 解答第41题 —— 缺失的第一个正数（First Mis

levius 发布于2019-08-23 16:46 / 2131人阅读

摘要：小鹿题目算法思路桶排序思想。再遍历数组，从下标开始判断该下标是否存放规定的数据，如果不是则该下标就是这组数据中缺失的最小正整数。桶排序还可以实现在一组数据中查找重复的数据。

Time：2019/4/6
Title: First Missing Positive
Difficulty: Difficulty
Author: 小鹿

题目：First Missing Positive

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

Note:

Your algorithm should run in O(n) time and uses constant extra space.

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

Solve：

▉ 算法思路：

桶排序思想。

遍历第一遍数据，将数据存放到与下标相同的位置，遍历第二遍数据，判断每个下标对应的数据是否为下标值。如果不是，该数值就是当前确实的最小正整数;当数组遍历完还有没找到，那么数组的长度 + 1 就是缺失的最小正整数值。

▉ 算法步骤：

1、把数组的每一个下标当做是一个桶，每个桶只能存放一个数据（每个下标对应一个数据），我们规定桶中的数据和下标的对应关系是 0 下标对应数据1,1下标对应数据2，2下标对应数据3......，题目要求我们在O(n)的时间复杂度内找出一组数据中缺失的最小正整数。

2、遍历第一遍数组中的数据，按照步骤 1 的规定，先判断两个当前下标对应的数据是否为规定的数据，如果不是，我们将该数据存放到规定的下标对应的数组中。然后交换的数据继续进行判断，直到该数据放到规定下标的数组中为止（小于等于 0 和数据大于数组长度的除外）。

3、再遍历数组，从下标 0 开始判断该下标是否存放规定的数据，如果不是则该下标就是这组数据中缺失的最小正整数。

4、如果数组中的数据都匹配对应的下标，那么最小正整数就是数组长度加一。

▉ 代码实现：

/**
* @param {number[]} nums
* @return {number}
* 边界条件：
* 1) 判断传入的数组是否为空。 
* 2) 判断数组中的数据只有 1 个。
* 3) 交换数据时，判断相同数据的处理。
*/
var firstMissingPositive = function(nums) {
    //遍历数组
    for(let i = 0;i < nums.length;i++){
        //如果当前的数据不对应正确的下标 + 1 && 数据大于 0 && 长度小于等于数组
        while(nums[i] != i+1 && nums[i] > 0 && nums[i] <= nums.length){
            //判断该数据对应正确位置的数据是否相同
            if(nums[nums[i]-1] == nums[i]) {
                //如果相同，将该下标对应的元素置为 0
                nums[i] = 0;
                break;
            }
            //如果不重复，就交换数据
            let temp = nums[nums[i] - 1];
            nums[nums[i] - 1] = nums[i];
            nums[i] = temp;
        }
    }
    //遍历所有数据,找出缺失的最小正整数
    let index = 0;
    for(; index < nums.length; index++){
        if(nums[index] !== index+1){
            break;
        }
    }
    return index+1;
};

//测试
let arr =[];
console.log(firstMissingPositive(arr))

▉ 总结：

1、桶排序的思想。

2、桶排序还可以实现在一组数据中查找重复的数据。

欢迎一起加入到 LeetCode 开源 Github 仓库，可以向 me 提交您其他语言的代码。在仓库上坚持和小伙伴们一起打卡，共同完善我们的开源小仓库！
Github：https://github.com/luxiangqia...

欢迎关注我个人公众号：「一个不甘平凡的码农」，记录了自己一路自学编程的故事。

云服务器 GPU云服务器小白的第一本python 代表企业的第二级域名为 javascript算法题汇编语言程序设计第二版课后题答案

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/103274.html

LeetCode41.缺失的第一个正数 JavaScript

摘要：给定一个未排序的整数数组，找出其中没有出现的最小的正整数。示例输入输出示例输入输出示例输入输出答案参考给定一个未排序的整数数组，找出其中没有出现的最小的正整数。示例 1: 输入: [1,2,0]输出: 3 示例 2: 输入: [3,4,-1,1]输出: 2 示例 3: 输入: [7,8,9,11,12]输出: 1 答案参考： /** * @param {number[]} num...

ymyang 2019-08-23 15:17 评论0 收藏0
LeetCode 之 JavaScript 解答第8题 —— 字符串转换整数（String to

摘要：当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。数字前正负号要保留。 Time：2019/4/19Title: String To IntegerDifficulty: MediumAuthor: 小鹿题目：String To Integer（字...

zhisheng 2019-08-23 17:03 评论0 收藏0
41. 缺失的第一个正数

摘要：问题问题描述给定一个未排序的整数数组，找出其中没有出现的最小的正整数。原因就在于使用的内置的函数的复杂度超过的比如的复杂度就是。问题问题描述给定一个未排序的整数数组，找出其中没有出现的最小的正整数。说明你的算法的时间复杂度应为O(n)，并且只能使用常数级别的空间。解答首先因为只能使用常数级别的空间，就不能再建新的O(n)级的list，set等。然后就想到将列表去重去除非...

enali 2019-07-30 18:37 评论0 收藏0
LeetCode 之 JavaScript 解答第142题 —— 环形链表 II（Linked Li

摘要：说明不允许修改给定的链表。算法思路题目要求返回单链表中存在循环链表的位置。首先，先判断该单链表是否存在循环链表用两个快慢指针分别指向链表的头部，每次移动两步，每次移动一步，移动的步数是的两倍。 Time：2019/4/8Title: Linked List Cycle IIDifficulty: mediumAuthor:小鹿题目：Linked List Cycle II Giv...

whidy 2019-08-23 16:51 评论0 收藏0
LeetCode 之 JavaScript 解答第141题 —— 环形链表 I（Linked Lis

摘要：小鹿题目算法思路两种解题思路哈希表法遍历链表，没遍历一个节点就要在哈希表中判断是否存在该结点，如果存在，则为环否则，将该结点插入到哈希表中继续遍历。 Time：2019/4/7Title: Linked List CycleDifficulty: Easy Author:小鹿题目：Linked List Cycle I Given a linked list, determine ...

wangjuntytl 2019-08-23 16:49 评论0 收藏0