本文主要是介绍手撕Hard--缺失的第一个正数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
😎 作者介绍：我是程序员行者孙，一个热爱分享技术的制能工人。计算机本硕，人工制能研究生。公众号：AI Sun，视频号：AI-行者Sun
🎈 本文专栏：本文收录于《深入浅出算法》系列专栏，相信一份耕耘一份收获，我会系统全面的分享算法课程，届时可以拳打字节，脚踢腾讯
🤓 欢迎大家关注其他专栏，我将分享Web前后端开发、人工智能、机器学习、深度学习从0到1系列文章。
🖥 随时欢迎您跟我沟通，一起交流，一起成长、进步！
给你一个未排序的整数数组
nums，请你找出其中没有出现的最小的正整数。请你实现时间复杂度为
O(n)并且只使用常数级别额外空间的解决方案。示例 1：
输入：nums = [1,2,0] 输出：3 解释：范围 [1,2] 中的数字都在数组中。示例 2：
输入：nums = [3,4,-1,1] 输出：2 解释：1 在数组中，但 2 没有。示例 3：
输入：nums = [7,8,9,11,12] 输出：1 解释：最小的正数 1 没有出现。提示：
1 <= nums.length <= 105-231 <= nums[i] <= 231 - 1
方法一：最简单的思路，hash表把所有正数存下来，然后遍历hash表，缺失值就找到了。（比官方的易理解，官方是用数组标记）
class Solution {
public:int firstMissingPositive(vector<int>& nums) {unordered_map<int,int> hash;for(int i=0;i<nums.size();i++){if(nums[i]>0)hash[nums[i]]++;}int res=0;while(hash[++res]);return res;}
};leetcode官方 ：
class Solution {
public:int firstMissingPositive(vector<int>& nums) {int n = nums.size();for (int& num: nums) {if (num <= 0) {num = n + 1;}}for (int i = 0; i < n; ++i) {int num = abs(nums[i]);if (num <= n) {nums[num - 1] = -abs(nums[num - 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(); // 获取数组的长度// 第一次遍历数组，将每个正整数 nums[i] 放置到索引为 nums[i] - 1 的位置上// 即将 1 放到索引 0，将 2 放到索引 1，以此类推，直到 n 放到索引 n - 1for (int i = 0; i < n; ++i) {// 只处理大于 0 且小于等于 n 的元素，并且确保 nums[i] 不在正确位置上while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {swap(nums[nums[i] - 1], nums[i]); // 将 nums[i] 放到正确的位置上}}// 第二次遍历数组，找到第一个不在正确位置上的数，即缺失的最小正整数for (int i = 0; i < n; ++i) {if (nums[i] != i + 1) { // 如果 nums[i] 不等于 i + 1，表示缺失 i + 1return i + 1;}}// 如果数组中包含 1 到 n 的所有正整数，则缺失的是 n + 1return n + 1;}
};
这篇关于手撕Hard--缺失的第一个正数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
