力扣---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
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[nums[i]-1]!=nums[i]){
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;
}
};
第一次遍历(重新排序)
我们需要把所有在 [1, n]
范围内的正整数 x放到索引 x−1的位置上。我们利用一个 while
循环来完成这个任务。
-
条件判断:
nums[i] > 0
: 只考虑正整数。nums[i] <= n
: 只考虑不大于数组长度n
的整数。nums[nums[i] - 1] != nums[i]
: 确保nums[i]
应该放在nums[nums[i] - 1]
位置上,并且这个位置上还没有正确的值。
-
交换: 将
nums[i]
放到它正确的位置上,即nums[nums[i] - 1]
。每次交换后,我们还需要重新检查当前位置的值是否已经在正确的位置上,所以需要用while
循环。
例如,对于数组 [3, 4, -1, 1]
:
- 初始数组:
[3, 4, -1, 1]
- 第一次交换:
[ -1, 4, 3, 1]
(将 3 放到索引 2) - 第二次交换:
[-1, 1, 3, 4]
(将 4 放到索引 3) - 第三次交换:
[1, -1, 3, 4]
(将 1 放到索引 0)
第二次遍历(查找缺失的正整数)
经过第一次遍历后,数组应该是部分有序的,即 nums[i]
应该等于 i+1
。
- 条件判断:
- 遍历数组,如果
nums[i] != i + 1
,说明i + 1
是缺失的最小正整数。
- 遍历数组,如果
例如,对于上述的有序数组 [1, -1, 3, 4]
:
- 遍历到
i = 1
时,nums[1]
应该是2
,但实际上是-1
,所以2
是缺失的最小正整数。
返回结果
- 如果所有位置上的元素都是正确的,说明数组包含
[1, n]
的所有整数,则缺失的最小正整数是n + 1
。
总结
这个算法的时间复杂度是 O(n),因为每个元素最多交换一次。而且使用的是原地交换,所以额外空间复杂度是 O(1)。通过这个过程,我们可以有效地找到缺失的最小正整数。
原文地址:https://blog.csdn.net/weixin_48664959/article/details/140327852
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!