PAT_1144

1144 The Missing Number

题目描述

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:

1
2
10
5 -25 9 6 1 3 4 2 5 17

Sample Output:

1
7

思路

寻找不出现在列表中的最小的数字,那么直接暴力判断有没有出现在列表中即可

程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#define INF 0x3f3f3f3f

using namespace std;

const int maxn = 1e5+5;
typedef long long ll;
int a[maxn],n;

int main()
{
scanf("%d",&n);
for(int i =0 ;i < n;i ++)
scanf("%d",a+i);
int index = 0;
sort(a,a+n);
for(int i =1 ;i < maxn;i ++)
if(*lower_bound(a,a+n,i) != i)
{
printf("%d\n",i);
return 0;
}
}
-------------本文结束感谢您的阅读-------------
显示 Gitment 评论