​LeetCode刷题实战41:缺失的第一个正数

算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !

今天和大家聊的问题叫做 缺失的第一个正数,我们先来看题面:

https://leetcode-cn.com/problems/first-missing-positive/

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

题意

给你一个未排序的整数数组,请你找出其中没有出现的最小的正整数 。你的算法的时间复杂度应为O(n),并且只能使用常数级别的额外空间。

样例

示例 1:

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

示例 2:

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

示例 3:

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

题解

由于线性时间和常数空间的要求,我们开不了数组,用不了哈希表,不能排序。能用的就只有数组本身以及额外常数个变量。。。
我们考虑如果整数都出现,那么最后数组排列应该是[1,2,3,4,5,…,n],每个都是递增1。于是乎,如果我们最后也排列成这种形式,那么只要不满足nums[i]-nums[i-1]不等于1,那么就找到了最小的未出现的整数,但是我们没法排序。
所以我们可以强行另数组下标和存的值产生联系-> 令数字i出现在下标为i-1的位置,如果会越界则不做处理。
比如[3,4,-1,1]->[-1,4,3,1]->[-1,1,3,4]->[1,-1,3,4];

class Solution {

public int firstMissingPositive(int[] nums) {
            for(int i=0;i<nums.length;){
                if(nums[i]>0&&nums[i]<=nums.length&&nums[i]!=nums[nums[i]-1]){
                    //确定nums[i]的值对应的下标不越界,同时排除num[i]本身位置正确或者nums[i]应该放入的位置nums[i]-1原本就是nums[i](如[1,1])

int index = nums[i];//
                    nums[i] = nums[index -1];
                    nums[index -1]=index;
                    //换位置之后需要继续判断换过来的值是否在对的位置上,因此不能i++;
                }else{
                    i++;
                }
            }
            for(int i=0;i<nums.length;i++){
                if(nums[i]!=i+1){
                    return i+1;
                }
            }
            return nums.length+1;
        }
    }

好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力。

上期推文:

LeetCode1-20题汇总,速度收藏!
LeetCode21-40题汇总,速度收藏!
LeetCode刷题实战40:组合总和 II
(0)

相关推荐

  • 算法创作|两数之和返回数组下标问题解决方法

    问题描述给定一个整数数组nums和一个整数目标值target,请你在该数组中找出和为目标值的那两个整数,并返回它们的数组下标.示例:输入:nums = [3,5,7,9],target = 14输出: ...

  • Leetcode刷题 2021.01.24

    Leetcode674 最长连续递增序列 给定一个未经排序的整数数组,找到最长且 连续递增的子序列,并返回该序列的长度. 连续递增的子序列 可以由两个下标 l 和 r(l < r)确定,如果对于 ...

  • LeetCode面试系列 第11天:No.645 - 错误的集合

    上一篇 LeetCode 面试题中,我们分析了一道简单的几何数学题.今天我们来分析一道集合相关的数学题. Leetcode 今天要给大家分析的面试题是 LeetCode 上第 645 号问题, Lee ...

  • ​LeetCode刷题实战278:第一个错误的版本

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • ​LeetCode刷题实战387:字符串中的第一个唯一字符

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • ​LeetCode刷题实战260:只出现一次的数字 III

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • ​LeetCode刷题实战258:各位相加

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • ​LeetCode刷题实战257:二叉树的所有路径

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • ​LeetCode刷题实战256:粉刷房子

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • ​LeetCode刷题实战262:行程和用户

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • ​LeetCode刷题实战255:验证前序遍历序列二叉搜索树

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • ​LeetCode刷题实战263:丑数

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...