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/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年5月10日
下一篇 2020年5月11日

相关推荐

  • leetcode60-第k个排列

    原题 给出集合 [1,2,3,…,n],其所有元素共有 n! 种排列。 按大小顺序列出所有排列情况,并一一标记,当 n = 3 时, 所有排列如下: "123" "132" "21…

    算法 2020年5月16日
    0110
  • leetcode540-有序数组中的单一元素

    原题 给定一个只包含整数的有序数组,每个元素都会出现两次,唯有一个数只会出现一次,找出这个数。 示例1: 输入: [1,1,2,3,3,4,4,8,8] 输出: 2 示例2: 输入…

    2020年2月25日
    0700
  • leetcode134-加油站

    原题 在一条环路上有 N 个加油站,其中第 i 个加油站有汽油 gas[i] 升。 你有一辆油箱容量无限的的汽车,从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[…

    算法 2020年2月16日
    080
  • 剑指offer46-把数字翻译成字符串

    原题 给定一个数字,我们按照如下规则把它翻译为字符串:0 翻译成 “a” ,1 翻译成 “b”,……,11 翻译成 “l”,……,25 翻译成 “z”。一个数字可能有多个翻译。请编…

    算法 2020年2月29日
    0300
  • leetcode123-买卖股票的最佳时机III

    原题 给定一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。 注意: 你不能同时参与多笔交易(你…

    算法 2020年6月16日
    01540
  • leetcode701-二叉搜索树中的插入操作

    原题 给定二叉搜索树(BST)的根节点和要插入树中的值,将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 保证原始二叉搜索树中不存在新值。 注意,可能存在多种有效的插入方式,只…

    算法 2020年1月16日
    0100
  • leetcode409-最长回文串

    原题 给定一个包含大写字母和小写字母的字符串,找到通过这些字母构造成的最长的回文串。 在构造过程中,请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。 注意:假设字符串的长…

    算法 2020年3月19日
    0570
  • leetcode167-两数之和II-输入有序数组

    原题 给定一个已按照 升序排列 的有序数组,找到两个数使得它们相加之和等于目标数。 函数应该返回这两个下标值index1和index2,其中index1必须小于index2。 说明…

    算法 2019年11月20日
    0190
  • leetcode198-打家劫舍

    原题 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会…

    算法 2020年5月29日
    060
  • leetcode80-删除排序数组中的重复项II

    原题 给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素最多出现两次,返回移除后数组的新长度。 不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外…

    算法 2020年5月26日
    0140

发表回复

登录后才能评论