wap网站开发和自适应,博客用wordpress对吗,网站开发与维护专员岗位职责,我想接加工单题目描述#xff1a;
给你一个未排序的整数数组 nums #xff0c;请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。 示例 1#xff1a;
输入#xff1a;nums [1,2,0]
输出#xff1a;3示例 2#xff1a;
输…题目描述
给你一个未排序的整数数组 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 nums.length 5 * 105-231 nums[i] 231 - 1
通过次数
325.7K
提交次数
749K
通过率
43.5%
思路和题解
设数组长度为n则确实的第一个正数只能在[1,n1]的闭区间
思路一暴力搜索。时间O(n^2),空间O(1)不符合要求
依次判断[1,n]在不在数组里如果不在就返回那个不在的数如果都在就返回n1。代码。
//暴力循环
class Solution {
public:int firstMissingPositive(vectorint nums) {int nnums.size();for(int i1;in;i){bool flagfalse;for(int j0;jn;j){if(nums[j]i){flagtrue;break;}}if(!flag) return i;}return n1;}
};思路二普通的哈希表。时间O(n),空间O(n)不符合要求。
用一个长度为n的数组来标记[1,n]有没有出现过。
//普通哈希表
class Solution {
public:int firstMissingPositive(vectorint nums) {int nnums.size();vectorbool hash(n,false);for(int i0;in;i){//出现了就标记为真if(nums[i]0nums[i]n)hash[nums[i]-1]true;}for(int i0;in;i){if(hash[i]false) return i1;}return n1;}
};
思路三原地哈希表。时间O(n),空间O(1)
思路二是我们能想到的比较好的办法了但是空间复杂度还是不能达到要求那我们怎么来优化这个空间复杂度O(n)呢要知道只用O(n)的时间复杂度也就是只用一层的循环要找出缺失的第一个正数的话不用其他空间来存储正数存在的状态时不可能的。既然必须要用空间来存储一些状态又只能额外使用常数的空间那我们只好拿给定的数组nums作为存储状态的空间。也就是说用原数组nums作为哈希表。
问题是怎么标记一个正数是否出现的状态。对于num0numn的数num在[1,n]之外无论怎么变化都不会改变答案。那就干脆先把数组里所有0的数先变成n1之后再遍历数组把每个[1,n]内的数num对应下标处都改为负数。最后再遍历一遍数组对应元素不为负就说明这个数对应的位置是第一个缺失的正数。
class Solution {
public:int firstMissingPositive(vectorint nums) {//原地哈希表//第一个缺失的数只能出现在[1,n1]的闭区间里int nnums.size();for(int i0;in;i){//若出现负数或零或大于n的数那第一个确实的数就在[1,n]if(nums[i]0) nums[i]n1;}for(int i0;in;i){//将[num-1]标记为负表示正数num没有缺失,numn时不用管int numabs(nums[i]);if(numn){nums[num-1]-abs(nums[num-1]);}}for(int i0;in;i){if(nums[i]0) return i1;}return n1;}
};
