力扣刷题--41.缺失的第一个正数【困难】
少则得，多则惑
题目描述
给你一个未排序的整数数组 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
思路分析
-
原地哈希
-
核心思想：将元素nums[i]尽可能地放到下标i上面
完整代码
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int n=nums.size();
//从0开始
for(int i=0;i<n;i++){
while(nums[i]>=0&&nums[i]<n&&nums[i]!=nums[nums[i]])
swap(nums[i],nums[nums[i]]);
}
//从1开始
for(int i=1;i<n;i++)
{
if(nums[i]!=i)
return i;
}
return nums[0]==n?n+1:n;
}
};
代码解释
-
初始化变量：
int n = nums.size();
-
n记录数组nums的大小。
-
第一次遍历：原地哈希：
for(int i = 0; i < n; i++)
while(nums[i] >= 0 && nums[i] < n && nums[nums[i]] != nums[i])
swap(nums[i], nums[nums[i]]);
-
这个循环的作用是将数组中的每个元素尽可能地放置在它应该在的位置上。
-
while循环的条件是： -
nums[i] >= 0：元素值必须是非负数（正整数）。 -
nums[i] < n：元素值必须小于数组的大小n，因为数组的索引是从0到n-1。 -nums[nums[i]] != nums[i]：元素值nums[i]应该放置在索引nums[i]处，但当前位置不是它。 -
swap(nums[i], nums[nums[i]])：将元素nums[i]交换到它应该在的位置nums[nums[i]]。举个例子：
-
如果 nums[i]是1，那么它应该被放置在索引1处。如果nums[i]是2，那么它应该被放置在索引2处。 -
这个过程会一直进行，直到 nums[i]无法再交换为止。
-
-
第二次遍历：寻找第一个缺失的正整数：
for(int i = 1; i < n; i++)
if(nums[i] != i)
return i;
-
从索引
1开始遍历数组，检查每个位置i的值是否等于i。 -
如果
nums[i] != i，说明索引i处没有放置正确的值，即i是第一个缺失的正整数，返回i。
-
处理边界情况：
return nums[0] == n ? n + 1 : n;
-
如果数组中所有的正整数都按顺序放置在正确的位置上，那么第一个缺失的正整数应该是
n。 -
但我们需要检查
nums[0]是否等于n： -
如果
nums[0] == n，说明数组中包含n，那么第一个缺失的正整数应该是n+1。 -
否则，第一个缺失的正整数是
n。
-
原地哈希：
-
这个算法的核心思想是，将数组中的每个正整数放到它应该在的位置上。比如，数字 1应该放在索引1处，数字2应该放在索引2处，依此类推。如果某个位置上的数字不是它应该在的位置，就把它放到正确的位置上。
-
寻找缺失的正整数：
-
经过上面的原地哈希操作后，数组中的每个正整数都应该在它应该在的位置上。如果某个位置上的数字不是它应该在的位置，那么这个位置的索引就是第一个缺失的正整数。
-
处理特殊情况：
-
如果数组中的所有正整数都按顺序放置在正确的位置上，那么第一个缺失的正整数应该是数组的大小 n或n+1，具体取决于nums[0]的值。