Give

nn

n non-negative integers, please find the least non-negative integer that doesn’t occur in the

nn

n numbers.

输入：

The first line is an integer

TT

T, representing the number of test cases.

For each test case:

The first line of each test case is an integer

nn

n.

The second line of each test case are

nn

n non-negative integers

aia_i

a

i

题意:给你n个数,找出缺失的第一个非负整数.

题解:用map标记已经出现过数,然后从 0 到 1<<31枚举,

#include 
    
     using namespace std;typedef long long ll;map
     
       m;int main(){    int t;    cin>>t;    while(t--){        m.clear();        int n;        cin>>n;        unsigned tmp;        for(int i=1;i<=n;i++){            scanf("%u",&tmp);            m[tmp]=1;        }        unsigned i=0;        while(i<=(1<<31)){            if(m[i]==0){                printf("%u\n",i);                break;            }            i++;        }    }    return 0;    }
     
    

--------------分割线-5/2----------

放上一个不用stl的算法.

题解:将n个数sort后

1) 如果第一个不是 0 那就输出 0,否则跳到 2)

2) 枚举这n个数,如果 a[i]-a[i-1]>1 ,说明 a[i] 和 a[i] 之间有其他数,输出 a[i]+1 ,枚举完所有数后都没有,则跳到 3)

3) 枚举完n个数后都发现都是连续的,那么可以知道 缺少的最小的非负数为 a[n]+1

#include 
    
     using namespace std;const int N=2e5+5;int a[N];int main(){    int t;    cin>>t;    while(t--){        int n;cin>>n;        for(int i=1;i<=n;i++){            scanf("%d",&a[i]);        }        sort(a+1,a+1+n);        if(a[1]!=0){            puts("0");        }        else{            int k=0;            for(int i=1;i<=n;i++){                if(a[i]-a[i-1]>1){                    printf("%d\n",a[i-1]+1);                    k=1;                    break;                }            }            if(k==0){                printf("%d\n",a[n]+1);            }        }    }    return 0;}