思路:我的初步想法是先对数组排序,然后找到第一个正数的位置,从1开始顺序比对:哪个没出现就是答案。
代码:
class Solution {
public:int firstMissingPositive(vector<int>& nums) {sort(nums.begin(),nums.end());int ans=0;int zs_poition=0;for(int i=0;i<nums.size();i++){if(nums[i]>0){zs_poition=i;//第一个正整数的位置,从这里开始比对break;}}for(int i =zs_poition,zzs=1;i<nums.size();i++){if(zzs!=nums[i]){ans=zzs;break;}if(i==nums.size()-1){ans=zzs+1;}zzs++;}return ans;}
};
巨呆逼的方法 还错了。。。。。。。
分析了一下错误样例,原因就是没有考虑重复数字,可以排序后进行一次去重。也可以在后面专门处理一下有重复数字的情况。
class Solution {
public:int firstMissingPositive(vector<int>& nums) {sort(nums.begin(),nums.end());int ans=0;int zs_poition=0;for(int i=0;i<nums.size();i++){ if(nums[i]>0){zs_poition = i;//第一个正整数的位置,从这里开始比对break;}}for(int i =zs_poition,zzs=1;i<nums.size();i++) {// 处理重复数字 if(zzs!=nums[i]){if(i==0){ans=zzs;break;}else if(i>0&&nums[i]!=nums[i-1]){ans=zzs;break;}else{zzs--;}}if(i==nums.size()-1){ans=zzs+1;}zzs++;}return ans;}
};
现在是全部过了。但是用了排序,算是作弊了吧,排序是nlogn 题目要求时间复杂度On,且常数级别的空间复杂度。
看看题解:
都太巧妙了。
我们用排序的也太复杂了:
这样不用考虑重复的问题。但是都是不满足O(n)或者另外开了空间的。
但我们也来写一些代码来练一下手吧。
法一:哈希表
注意 哈希表的增加元素是用insert()方法。
这里用一个简单的set就可以了,只要存键。
class Solution {
public:int firstMissingPositive(vector<int>& nums) {unordered_set<int> q;for(auto t:nums){q.insert(t);}for(int i=1;;i++){if(!q.count(i)){return i;}}}
};
法二On^2就算了
实在是太妙了下面这个解法,一定要温故而知新:
主要思路:
要明白,缺失的正整数一定在[1,N+1]中,其中N 为数组的长度。
这道题的灵感就是从哈希表中得到的,可以对数组进行标记。
首先,由于缺失的正整数一定在[1,N+1]中:若[1,N]都存在,则缺失的为N+1,否则,缺失的正整数就在[1,N]中。
首先,对数组中小于1的数进行赋值,就赋值为N+1即可。
然后遍历一次数组,将遍历到的值在[1,N]中的对应位置加上负号(打上标记),代表这个位置所代表的正整数是在数组中存在的。
由于会出现负数,(被标记过了),故在进行遍历的时候,取绝对值来判断。
最后,再遍历一遍数组,若所有的位置都被打上了标记(全部为负数),则第一个缺失的正整数即为N+1。
这样子写的代码就是O(n)且没有开其他的空间。
代码:
class Solution {
public:int firstMissingPositive(vector<int>& nums) {int n =nums.size();for(int i=0;i<n;i++){if(nums[i]<1){nums[i]=n+1;//处理一下本来的负数和0,以免影响标记}}for(int i=0;i<n;i++)//遍历整个数组{int t=abs(nums[i]);if(t>=1&&t<=n){nums[t-1]=-abs(nums[t-1]);//如果满足要求,将对应位置改为负数,已经是负的不用再处理一次。}}int ans=0;for(int i=0;i<n;i++)//重新遍历{if(nums[i]>0)//有大于零的 则i+1则为缺的那个正整数{ans=i+1;break;}}return ans==0?n+1:ans;//若ans还是等于0,则代表1~N在数组中都有,缺失的正整数为N+1;}
};