leetcode 41. First Missing Positive

smallStone 发布于2019-08-15 10:51 / 2211人阅读

摘要：题目要求在数组中找到第一个漏掉的正整数。思路一暴力排序后寻找排序后寻找显然是最快的。这些临时变量可以是排除出的量，也可以是有效量。当遇到的数字为有效数字时，则将该数字放到对应当前起始下标其相应的位置上。

题目要求

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

For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

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

在数组中找到第一个漏掉的正整数。如果可以的话，使用O(N)的时间复杂度和O(1)的空间复杂度。

思路一：暴力排序后寻找

排序后寻找显然是最快的。排序的时间复杂度要依靠java底层的依赖。之后再用O(N)的时间复杂度找到第一个漏掉的整数后即退出遍历。

    public int firstMissingPositive(int[] nums) {
        int size = nums.length;
        if(size == 0) return 1;
        Arrays.sort(nums);
        int positive = 1;
        for(int i = 0 ; ipositive) return positive;
            positive++;
        }
        return positive;
        
    }

思路二：O(1)空间复杂度

要实现这种空间复杂度，一般需要有限数量的临时变量来记录遍历的有效范围，再利用原有题目中的数据结构来存储其余的临时变量。这些临时变量可以是排除出的量，也可以是有效量。在这里我用leftPointer记录有效数字的开始下标（即将无效数字转移到leftPointer左侧），利用maxPositive记录数组最大有效整数（换句话说，如果一个数组的大小为9，则该数组的最大first missing positive integer即为10，一旦数组中出现重复或是小于1或是大于9的数字，该数字即为无效数字)。当遇到的数字为有效数字时，则将该数字放到对应当前起始下标leftPointer其相应的位置上。

    public int firstMissingPositive2(int[] nums){
        int size = nums.length;
        int positive = 1;
        int leftPointer = 0;
        int maxPositive = size;
        while(leftPointer maxPositive || nums[leftPointer] < positive || nums[leftPointer]==nums[leftPointer+nums[leftPointer]-positive]){
                leftPointer++;
                maxPositive--;
            }else{
                int temp = nums[leftPointer];
                nums[leftPointer] = nums[leftPointer+temp-positive];
                nums[leftPointer+temp-positive] = temp;
            }
        }
        return positive;
    }

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~

GPU服务器私有云 Positive missing 事件 41 Leetcod

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

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

[LeetCode] 41. First Missing Positive

Problem Given an unsorted integer array, find the smallest missing positive integer. Example 1: Input: [1,2,0]Output: 3Example 2: Input: [3,4,-1,1]Output: 2Example 3: Input: [7,8,9,11,12]Output: 1Note...

30e8336b8229 2019-08-16 13:56 评论0 收藏0
LeetCode 之 JavaScript 解答第41题 —— 缺失的第一个正数（First Mis

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

levius 2019-08-23 16:46 评论0 收藏0
[LintCode] First Missing Positive

摘要：找第一个缺失的正整数，只要先按顺序排列好，也就是，找到第一个和不对应的数就可以了。注意数组的从开始，而正整数从开始，所以重写排列的时候要注意换成，而就是从开始的数组中的元素。 Problem Given an unsorted integer array, find the first missing positive integer. Example Given [1,2,0] re...

snifes 2019-08-14 15:20 评论0 收藏0
[Leetcode] Missing Number and Missing First Positi

摘要：代码映射法复杂度时间空间思路核心思想就是遍历数组时，将每个元素，和以该元素为下标的元素进行置换，比如第一个元素是，就将它置换到下标为的地方，而原本下标为的地方的元素就换到第一个来。 Missing Number Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one t...

Forest10 2019-08-14 12:24 评论0 收藏0
leetcode376. Wiggle Subsequence

摘要：题目要求扭动序列是指数组中的相邻两个元素的差保证严格的正负交替，如数组中相邻两个元素的差为，满足扭动序列的要求。现在要求从一个数组中，找到长度最长的扭动子序列，并返回其长度。即前一个元素和当前元素构成下降序列，因此代码如下题目要求 A sequence of numbers is called a wiggle sequence if the differences between ...

CoffeX 2019-08-16 17:10 评论0 收藏0