1144 The Missing Number (20分)
Given N integers, you are supposed to find the smallest positive integer that is NOT in the given list.
Input Specification:
Each input file contains one test case. For each case, the first line gives a positive integer N (≤105). Then N integers are given in the next line, separated by spaces. All the numbers are in the range of int.
Output Specification:
Print in a line the smallest positive integer that is missing from the input list.
Sample Input:
代码语言：javascript复制10
5 -25 9 6 1 3 4 2 5 17Sample Output:
代码语言：javascript复制7法一：排序枚举法，先排序，然后答案从1开始枚举，模拟
代码语言：javascript复制#include<bits/stdc .h>
using namespace std;
#define ll long long
#define rg register ll
#define inf 2147483647
#define lb(x) (x&(-x))
ll sz[200005],n;
template <typename T> inline void read(T& x)
{
x=0;char ch=getchar();ll f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<3) (x<<1) (ch^48);ch=getchar();}x*=f;
}
inline ll query(ll x){ll res=0;while(x){res =sz[x];x-=lb(x);}return res;}
inline void add(ll x,ll val){while(x<=n){sz[x] =val;x =lb(x);}}//第x个加上val
ll a[100005];
int main()
{
cin>>n;
for(rg i=1;i<=n;i )read(a[i]);
sort(a 1,a 1 n);
ll ans=1,flag=0;
for(rg j=1;j<=n;j )
{
if(a[j]>0)
{
if(a[j]>ans)
{
cout<<ans<<endl;
flag=1;
break;
}
else if(a[j]==ans)ans ;
}
}
if(!flag)cout<<ans<<endl;
while(1)getchar();
return 0;
}法二：数学推导，给定数据范围是n个数，那么如果有大于n的数输入的话是无效的，因为最坏情况也只是1~n的一个随机排列，答案是n 1,所以可设初始答案上界为n 1,当输入的数小于0或者大于等于答案上界时，答案上界-1，因为可用的数变少了一个，很好理解，最后再遍历一遍即可
代码语言：javascript复制#include<bits/stdc .h>
using namespace std;
#define ll long long
#define rg register ll
#define inf 2147483647
#define lb(x) (x&(-x))
ll sz[200005],n;
template <typename T> inline void read(T& x)
{
x=0;char ch=getchar();ll f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<3) (x<<1) (ch^48);ch=getchar();}x*=f;
}
inline ll query(ll x){ll res=0;while(x){res =sz[x];x-=lb(x);}return res;}
inline void add(ll x,ll val){while(x<=n){sz[x] =val;x =lb(x);}}//第x个加上val
ll a[100005];
/*
int main()
{
cin>>n;
for(rg i=1;i<=n;i )read(a[i]);
sort(a 1,a 1 n);
ll ans=1,flag=0;
for(rg j=1;j<=n;j )
{
if(a[j]>0)
{
if(a[j]>ans)
{
cout<<ans<<endl;
flag=1;
break;
}
else if(a[j]==ans)ans ;
}
}
if(!flag)cout<<ans<<endl;
while(1)getchar();
return 0;
}
*/
int main()
{
cin>>n;
ll r=n 1;
for(rg j=1;j<=n;j )
{
ll x;
read(x);
if(x>=1&&x<r)a[x]=1;
else r--;
}
for(rg i=1;i<=r;i )if(!a[i])
{
cout<<i<<endl;
break;
}
while(1)getchar();
return 0;
}
