leetcode41-缺失的第一个正数

原题

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

示例 1:

输入: [1,2,0] 输出: 3

示例 2:

输入: [3,4,-1,1] 输出: 2

示例 3:

输入: [7,8,9,11,12] 输出: 1

提示:

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

解法

该题解同步发于leetcode:Java:比官方题解少一次循环

思想

见代码部分

代码

首先这道题有一个隐含条件:如果数组的大小为n,则缺失的第一个正数一定小于或等于n+1(取值最大的情况是数组中的数从1开始连续)

如果不限制常数级别的额外空间,可以使用bitmap的思想去做,如下:

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        //下标对应出现的数-1
        int[] exist = new int[n+1];
        for(int i:nums){
            if(i<=0 || i > n) continue;
            exist[i-1] = 1;
        }
        for(int i = 0;i<n+1;i++){
            if(exist[i]==0) return i+1;
        }
        return 0;
    }
}

但是限制了常数级别的额外空间,可以思考一种替换bitmap的原地解法:

既然要原地,肯定需要在原数组上判断当前下标代表的正数是否出现,但又不能修改它的值,因为遍历的时候会用到,可以想到通过修改它的符号来判断。相较于新建一个数组作为bitmap去重的区别是,存在不存在不通过1或0标识,而是通过正负号标识(负号标识出现过,正号标识没出现)

但是数组中存在一些数原来就是负号的,可以先遍历一次让它们都变成正数,0也要变成一个正数,否则无法通过改变符号识别该下标代表的元素是否出现。但变成哪个正数值得考量,否则再次遍历有可能把他们当作数组中原有的数处理,那么就可以把它们设为n+1,因为n+1大于数组的长度,不会映射到数组中的位,可以不进行处理:

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        //先将原来的负数的数置为 `n+1`
        for(int i = 0; i < nums.length ; i++){
            if(nums[i]<=0 ) {
                nums[i] = n+1;
            }
        }
        for(int i = 0; i < nums.length ; i++){
            int num = Math.abs(nums[i]);
            //绝对值大于数组长度的不处理
            if(num<=n && nums[num-1]>0) 
                nums[num-1] = -nums[num-1];
        }
        for(int i = 0;i<n;i++){
            if(nums[i]>0) return i+1;
        }
        return n+1;
    }
}

成功将官方题解的O(4N)优化成O(3N)~~~

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode41-%e7%bc%ba%e5%a4%b1%e7%9a%84%e7%ac%ac%e4%b8%80%e4%b8%aa%e6%ad%a3%e6%95%b0/

发表回复

登录后才能评论