首页 > 其他分享 >LeetCode题练习与总结:缺失的第一个正数

LeetCode题练习与总结:缺失的第一个正数

时间:2024-03-22 23:31:17浏览次数:29  
标签:代码 遍历 正整数 复杂度 缺失 数组 正数 LeetCode

一、题目

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

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

二、解题思路

  1. 遍历数组:首先,我们需要遍历数组,找到所有负数和零,并将它们替换为一个特定的值(比如数组的最大值加一),这样我们就可以将问题简化为只考虑正整数。

  2. 标记数字:接下来,我们将数组中的数字与从1开始的正整数进行比较。如果数组中的数字大于0且小于或等于数组的长度,我们将其视为一个标记,将数组中对应位置的值变为负数。这样做的目的是标记出所有已经出现的正整数。

  3. 找出未标记的数字:经过上述步骤,数组中值为正的数字对应的是未出现的正整数。我们再次遍历数组,找到第一个正数的位置,这个位置的索引加1就是缺失的最小正整数。

三、具体代码

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;

        // Step 1: Replace all negative numbers and zeros with a large number
        for (int i = 0; i < n; i++) {
            if (nums[i] <= 0) {
                nums[i] = n + 1;
            }
        }

        // Step 2: Mark the numbers as present by flipping the sign
        for (int i = 0; i < n; i++) {
            int num = Math.abs(nums[i]);
            if (num <= n) {
                nums[num - 1] = -Math.abs(nums[num - 1]);
            }
        }

        // Step 3: Find the first positive index
        for (int i = 0; i < n; i++) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }

        // If all numbers are present, the answer is n + 1
        return n + 1;
    }
}

四、时间复杂度和空间复杂度

1. 时间复杂度
  • 代码中包含了三个循环,每个循环都遍历了数组中的每个元素一次。
  • 因此,总的操作次数是三次数组长度,即 3n,这使得时间复杂度为 O(n)。
2. 空间复杂度
  • 代码中没有使用任何额外的数据结构或变量来存储除了输入数组之外的信息。
  • 所有的操作都是在原数组上进行的,因此空间复杂度是常数级别,即 O(1)。

五、总结知识点

  1. 数组操作:代码主要处理数组,包括数组的遍历、赋值和条件判断。这是解决此类问题的基础。

  2. 原地修改:算法在不使用额外空间的情况下对输入数组进行原地修改。这意味着所有的操作都是在输入数组上直接进行的,而不是创建新的数组或使用其他数据结构。

  3. 条件判断:代码中使用了条件判断来检查数组中的元素是否为非正数,并将其替换为一个大于数组长度的数,这样做是为了在后续步骤中能够区分正整数和非正整数。

  4. 数学函数Math.abs() 函数被用来获取数值的绝对值,这是为了确保在标记数组时不区分正负号。

  5. 位掩码:通过将数组中的正整数取反(即将正数变为负数),算法实际上使用了位掩码的技术来标记数组中已经出现过的正整数。这是一种常见的位操作技巧。

  6. 边界检查:在替换非正数为一个特定值时,代码检查了这个值是否小于或等于数组的长度,这是为了避免越界错误。

  7. 循环控制:代码中使用了嵌套循环和简单的条件语句来控制循环的执行流程,这是编程中常见的控制结构。

  8. 返回值:最后,根据数组的最终状态,算法返回缺失的最小正整数。如果没有找到任何正整数,则返回数组长度加一,这表示从1到n的所有正整数都出现了。

以上就是解决这个问题的详细步骤,希望能够为各位提供启发和帮助。

标签:代码,遍历,正整数,复杂度,缺失,数组,正数,LeetCode
From: https://blog.csdn.net/weixin_62860386/article/details/136694806

相关文章

  • LeetCode 55.跳跃游戏
    题目:方法一:给定数组中,每一位都可以确定出他所能跳到的最远距离(nums[i]+i)当然,前提是当前该位能够由前面的位置跳到我们可以定义一个总的最远距离(maxdistance)来记录(最远距离:当前能够到达的最大下标值)如果当前位置能够被跳到且其所能跳到的最远距离大于maxdistance,那么更新......
  • LeetCode刷题记录——day4
    https://leetcode.cn/problems/trapping-rain-water/description/?envType=study-plan-v2&envId=top-interview-150对于一个可以构成“碗”的序列,最后装满水的话应该和最短的一边齐平,那么可以左右各遍历一次,记录每个元素位置对应的最短边高度,再对比就可以得出左右哪边最短class......
  • 【LeetCode-153.寻找旋转排序数组的最小值】
    已知一个长度为 n 的数组,预先按照升序排列,经由 1 到 n 次 旋转 后,得到输入数组。例如,原数组 nums=[0,1,2,4,5,6,7] 在变化后可能得到:若旋转 4 次,则可以得到 [4,5,6,7,0,1,2]若旋转 7 次,则可以得到 [0,1,2,4,5,6,7]注意,数组 [a[0],a[1],a[2],...,a[n-1......
  • 算法打卡day25|回溯法篇05|Leetcode 491.递增子序列、46.全排列、47.全排列 II
     算法题Leetcode491.递增子序列题目链接:491.递增子序列大佬视频讲解:递增子序列视频讲解 个人思路和昨天的子集2有点像,但昨天的题是通过排序,再加一个标记数组来达到去重的目的。而本题求自增子序列,是不能对原数组进行排序的,因为排完序的数组都是自增子序列了。解决......
  • 【C++ leetcode】双指针问题
    1.  611.有效三角形的个数题目给定一个包含非负整数的数组nums,返回其中可以组成三角形三条边的三元组个数。题目链接.-力扣(LeetCode)画图和文字分析判断是否是三角形要得到三边,由于遍历三边要套三层循环,时间复杂度很大,所以这里我们需要借助双指针思想,可......
  • leetcode148. 排序链表-归并法
    148.排序链表题干给你链表的头结点head,请将其按升序排列并返回排序后的链表。示例1:输入:head=[4,2,1,3]输出:[1,2,3,4]示例2:输入:head=[-1,5,3,4,0]输出:[-1,0,3,4,5]示例3:输入:head=[]输出:[]提示:链表中节点的数目在范围[0,5*104]内-105<=N......
  • Leetcode 多数元素
    Day8第一题解题思路:数组中的数a出现次数若超过n/2,则排序后处于中间位置的元素一定是a。importjava.util.*;classSolution{publicintmajorityElement(int[]nums){//如果他超过n/2,则排序后处于中间位置。intn=nums.length;Arrays.......
  • LeetCode.59. 螺旋矩阵 II
    题目描述: 给你一个正整数 n ,生成一个包含 1 到 n2 所有元素,且元素按顺时针顺序螺旋排列的 nxn 正方形矩阵 matrix 。示例1:输入:n=3输出:[[1,2,3],[8,9,4],[7,6,5]]示例2:输入:n=1输出:[[1]]提示:1<=n<=20代码(Java): classSolution{publ......
  • LeetCodeHot100 二分查找 35. 搜索插入位置 74. 搜索二维矩阵 34. 在排序数组中查
    35.搜索插入位置https://leetcode.cn/problems/search-insert-position/description/?envType=study-plan-v2&envId=top-100-likedpublicintsearchInsert(int[]nums,inttarget){intleft=0;intright=nums.length-1;while(left<......
  • Leetcode 只出现一次的数据
    Day7第三题我的思路:利用Stream的distinct()方法找出不重复的,但后续思路想不出来。classSolution{publicintsingleNumber(int[]nums){intn=nums.length;IntStreamstream=Arrays.stream(nums);//转为stream流Stream<Integer>box......