PAT-ADVANCED1144——The Missing Number

我的PAT-ADVANCED代码仓：https://github.com/617076674/PAT-ADVANCED

原题链接：https://pintia.cn/problem-sets/994805342720868352/problems/994805343463260160

题目描述：

题目翻译：

1144 丢失的数字

给定N个整数，你需要找出缺失的最小的正整数。

输入格式：

每个输入文件包含一个测试用例。对每个测试用例，第一行给出一个正整数N(<= 10 ^ 5)。紧接着下一行给出N个整数，每个数字间由一个空格分隔。所有的数字都在int范围内。

输出格式：

在一行中输出输入列表中缺失的最小的正整数。

输入样例：

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

输出样例：

7

知识点：哈希表

思路：开一个大小为N + 1的数组nums，nums[i]保存值i

对于nums数组的初始化，我们初始化其所有值为-1。

对于读入的数字num，如果其在[0, N]范围内，则将其安放到nums数组的相应位置。

最后，我们只需从索引1开始遍历nums数组，找到第一个为-1的值，其索引就是缺失的第一个正数。

如果遍历完了整个nums数组我们都没有找到为-1的值，说明这N个数刚好是1 ~ N，那么我们就输出N + 1即可。

时间复杂度和空间复杂度均是O(N)。

C++代码：

#include<iostream>

using namespace std;

int main(){
	int N;
	scanf("%d", &N);
	int nums[N + 1];	//数组需要开N + 1大小，其中num[i]存储i 
	fill(nums, nums + N, -1);
	int num;
	for(int i = 0; i < N; i++){
		scanf("%d", &num);
		if(num >= 0 && num <= N){
			nums[num] = num;
		}
	}
	int i = 1;
	for(; i <= N; i++){
		if(nums[i] == -1){	//一旦找到了缺失的某个正数i,就输出 
			printf("%d\n", i);
			break;
		}
	}
	if(i > N){	//如果所有1 ~ N的所有正数都在，缺失的第一个正数一定是N + 1 
		printf("%d\n", i);
	} 
	return 0;
} 

C++解题报告：