LeetCode-41 缺失的第一个正整数

简介: LeetCode-41 缺失的第一个正整数

来源:力扣(LeetCode)

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

题目描述

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

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

 

示例 1:

输入:nums = [1,2,0]

输出:3

示例 2:

输入:nums = [3,4,-1,1]

输出:2

示例 3:

输入:nums = [7,8,9,11,12]

输出:1

 

提示:

1 <= nums.length <= 5 * 105

-231 <= nums[i] <= 231 - 1

 

解题思路

理论上并不存在时间复杂度为O(n) 空间复杂度为 O(1)的算法来做这道题,所以需要借助题目提供的nums来解,nums的范围为n,那么可以利用nums来判断1-n中是否有数字出现,如果没有,那么最小正整数为n+1,否则就是第一个缺失的数字。

一个思路是利用负号来记录1-n中数字是否出现过,先将所有负数变成n+1,然后遍历,如果数字x出现就将数字x对应的下标x-1的值设置为负数,等结束后第一个正数的下标加一就是缺失的数字。

另一个思路是重置归位,将1-n中的数字重置到nums对应的位置上并且继续重置被交换的数,那么第一个错位的数字就是缺失的数字。注意由于nums中数字可能相同,所以交换的双方相等就可以结束交换继续遍历。

代码展示

负号做标记

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for(int i = 0; i < n; i++)
        {
            if(nums[i] <= 0)
                nums[i] = n + 1;
        }
        for(int i = 0; i < n; i++)
        {
            if(abs(nums[i]) < n + 1)
                nums[abs(nums[i]) - 1] = nums[abs(nums[i]) - 1] < 0 ? nums[abs(nums[i]) - 1] : -1 * nums[abs(nums[i]) - 1];
        }
        for(int i = 0; i < n; i++)
            if(nums[i] > 0)
                return i + 1;
        return n + 1;
    }
};

置换

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for(int i = 0; i < n; i++)
        {
            while(nums[i] > 0 && nums[i] < n + 1 && nums[i] != nums[nums[i] - 1])
            {
                swap(nums[i], nums[nums[i] - 1]);
            }
        }
        for(int i = 0; i < n; i++)
            if(nums[i] != i + 1)
                return i + 1;
        return n + 1;
    }
};

 

运行结果

 

相关文章
|
2月前
Leetcode第41题(缺失的第一个正数)
这篇文章介绍了解决LeetCode第41题“缺失的第一个正数”的两种方法:使用哈希表和调整数组元素位置,以实现时间复杂度为O(n)且只使用常数级别额外空间的解决方案。
39 0
Leetcode第41题(缺失的第一个正数)
|
4月前
|
搜索推荐 索引 Python
【面试题】缺失的第一个整数
【面试题】缺失的第一个整数
34 0
|
7月前
leetcode-41:缺失的第一个正数
leetcode-41:缺失的第一个正数
36 0
|
算法 C语言 C++
【二分查找】1539. 第 k 个缺失的正整数
【二分查找】1539. 第 k 个缺失的正整数
97 0
|
算法 安全 Swift
LeetCode - #41 缺失的第一个正数
不积跬步,无以至千里;不积小流,无以成江海,Swift社区 伴你前行。如果大家有建议和意见欢迎在文末留言,我们会尽力满足大家的需求。
|
算法
leetcode:41.缺失的第一个正数
给定一个未排序的整数数组,找出其中没有出现的最小的正整数。
52 0
|
存储 算法
【题型总结】找到第n个自定义数 | 丑数系列 + 神奇数字
思路:对于对于任意一个丑数 x,其与任意的质因数(2、3、5)相乘,结果(2x、3x、5x)仍为丑数。因此可以使用优先队列(小根堆)存放丑数x,每次从队列取出最小值x,并将x所对应的2x、3x和5x入队。第n次出队的值即为第n个丑数
261 0
【题型总结】找到第n个自定义数 | 丑数系列 + 神奇数字
|
Java 测试技术
Java数字分类给定一系列正整数,请按要求对数字进行分类,并输出以下5个数字:A1 = 能被5整除的数字中所有偶数的和;A2 = 将被5除后余1的数字按给出顺序进行交错求和,即计算n1-n2+n3
Java数字分类给定一系列正整数,请按要求对数字进行分类,并输出以下5个数字:A1 = 能被5整除的数字中所有偶数的和;A2 = 将被5除后余1的数字按给出顺序进行交错求和,即计算n1-n2+n3
215 0
Java数字分类给定一系列正整数,请按要求对数字进行分类,并输出以下5个数字:A1 = 能被5整除的数字中所有偶数的和;A2 = 将被5除后余1的数字按给出顺序进行交错求和,即计算n1-n2+n3
|
算法 索引
Leetcode 40组合总数(回溯)Ⅱ&41缺失的第一个正数&42接雨水
给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
100 0
Leetcode 40组合总数(回溯)Ⅱ&41缺失的第一个正数&42接雨水