leetcode41-缺失的第一个正数

彭晨涛 • 2020年5月11日 00:23 • 算法 • 阅读 12

原题

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

示例 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/

leetcode41-缺失的第一个正数

原题

解法

思想

代码

相关推荐

发表回复