题目描述
输入$n$个自然数,求第一个没有出现的自然数。
算法
(先排序后枚举) $O(n\log n)$
读入后第一步,排序。
排序后维护一个$now$变量,如果:
- 目前的数=now,没有问题,now++;
- 目前的数=now-1,这个数=上一个数,啥都不用干;
- 否则,中间有空缺,输出$now+1$即可。
时间复杂度
- 读入:$O(n)$
- 排序:$O(n\log n)$
- 遍历:$O(n)$
C++ 代码
#include<bits/stdc++.h>
#define ns "-1"
#define fs(i,x,y,z) for(ll i=x;i<=y;i+=z)
#define ft(i,x,y,z) for(ll i=x;i>=y;i+=z)
#define ll long long
#define ull unsigned long long
#define db double
#define ms(a,b) memset(a,b,sizeof(a))
#define sz(a) sizeof(a)
using namespace std;
const int rw[]={-1,0,1,0,-1,1,-1,1},cl[]={0,1,0,-1,-1,1,1,-1};
const int N=100001,inf=0x7f7f7f7f;
const int daynum[]={114514,31,28,31,30,31,30,31,31,30,31,30,31};
int n,a[N],now;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;fs(i,1,n,1) cin>>a[i];
sort(a+1,a+n+1);
fs(i,1,n,1){
if(a[i]==now) now++;
else if(a[i]+1==now) ;
else{
cout<<now;
return 0;
}
}
cout<<now+1;
return 0;
}