A1144 The Missing Number (20 point(s))

寻找数组中缺少的第一个连续正整数--Set

1. 原文

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:

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

Sample output:

7

2. 解析

输入的值可能重复

set去重且从小到大排序 只能用for循环找到值

从idx=1开始 if(idx==*i) idx++;

最终idx值即为缺少的值

3. AC代码

#include<cstdio>
#include<set>
using namespace std;
const int maxn=100010;
set<int> num;
int main()
{
	int n;
	scanf("%d",&n);
	int a;
	for (int i = 0; i < n; ++i)
	{
		scanf("%d",&a);
		if (a>0)
		{
			num.insert(a);
		}
	}
	int idx=1;
	for (set<int>::iterator i = num.begin(); i != num.end(); ++i)
	{
		if (idx==*i)
		{
            idx++;
        }	
	}
    printf("%d",idx);
	return 0;
}

值要去重