leetcode 41. 缺失的第一个正数（困难）

​
​

作者简介：C/C++ 、Golang 领域耕耘者，创作者
个人主页：作者主页
活动地址：CSDN21天学习挑战赛
题目来源： leetcode官网
如果感觉博主的文章还不错的话，还请关注➕ 、点赞👍 、收藏🧡三连支持一下博主哦~~~

剑指offer有类似的题

💜 题目描述

给你一个未排序的整数数组 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开始依次枚举正整数，并判断其是否在哈希表中；

• 我们可以从 1 开始依次枚举正整数，并遍历数组，判断其是否在数组中。

方法二：
这题需要考虑常数的空间复杂度

需要用到数组元素原地交换的思想，直接上代码

💚 代码实现

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        unordered_set<int> S;
        for(auto x : nums) S.insert(x);

        int re = 1;
        while(S.count(re))  re ++;

        return re;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

方法二：

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        if(!n) return 1;

        for(auto& x : nums) 
            if(x != INT_MIN) x--;   // 下标映射一下

        // 交换到相应的位置上，剑指offer上有类似的题， 只用了常数空间
        for(int i =0; i < n; i ++)
            while(nums[i] >=0 && nums[i] < n && nums[i] != i && nums[i] != nums[nums[i]])
                swap(nums[i], nums[nums[i]]);

        for(int i = 0; i < n; i ++)
            if(nums[i] != i)
                return i + 1;
        
        return n + 1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

执行结果：

💙 时间复杂度分析

空间复杂度：使用了哈希表，空间复杂度为O(n)；
时间复杂度：线性时间复杂度，O(n)

如果觉得对你有帮助的话:
👍 点赞，你的认可是我创作的动力！
🧡 收藏，你的青睐是我努力的方向！
✏️ 评论，你的意见是我进步的财富！