41缺失的第一个正数【力扣】【C++】

题目描述

题目链接
给你一个未排序的整数数组 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
-2³¹ <= nums[i] <= 2³¹ - 1

思路

本题难点在于空间复杂度要求O(1)，所以不能创建数组、哈希表等数据结构，但是下面给出使用哈希表的代码：

class Solution {
public:int firstMissingPositive(vector<int>& nums) {unordered_set<int> un_set;for (int num : nums) {     //只放入正数，负数和0不重要if (num > 0) {un_set.insert(num);}}int i = 1;while (i <= nums.size()) {   //依次查找每个正数if (un_set.find(i) == un_set.end()) {return i;}i++;}return nums.size() + 1;   //[1,n]的正数都存在，所以返回n+1}
};

时间复杂度O(n)：遍历数组
空间复杂度O(n)：建立了哈希表

改进方法

由于不能建立哈希表，所以只能在原数组上操作，以保证空间复杂度O(1)。
如果有一个这样的数组，我么就能很快知道最小缺失的正数了：最小缺失正数 = 第一个不满足要求元素的小标 + 1，如下图所示：

所以步骤如下：
第一步：将数组变成排好序的数组，我们可以将每个正数i放在下标i - 1上面。如下图：

相关代码如下：

for (int i = 0; i < n; i++) {while (nums[i] > 0 && nums[i] <= n && nums[i] != nums[nums[i] - 1]) {swap(nums[i], nums[nums[i] - 1]);}
}

第二部：每个正数放好位置后，再次遍历，如果小标i对应的值不是i + 1就找到结果i+1。

for (int i = 0; i < n; i++) {if (nums[i] != i + 1) {   return i + 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 && nums[i] != nums[nums[i] - 1]) {swap(nums[i], nums[nums[i] - 1]);  //把值i放在小标i-1位置上}}for (int i = 0; i < n; i++) {if (nums[i] != i + 1) {   return i + 1;}}return n + 1;}
};

其中nums[i] != nums[nums[i] - 1]是为了防止死循环。
时间复杂度O(n)
空间复杂度O(1)

思路参考
相似题目：287. 寻找重复数