数据结构
2018-41
给定一个含 n（n≥1）个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数。例如，数组 {-5,3,2,3} 中未出现的最小正整数是 1；数组 {1,2,3} 中未出现的最小正整数是 4。
要求：
（1）给出算法的基本设计思想。
（2）根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。
（3）说明你所设计算法的时间复杂度和空间复杂度。
答案
【答案】
（1）算法基本设计思想：采用空间换时间策略，使用标记数组B（大小为n）记录数组A中是否出现了1到n之间的正整数。遍历A，若元素值在1到n内，则标记B中对应位置；否则忽略。然后遍历B，找到第一个未标记的位置（值为0），返回该位置索引加1即为结果；若B全部标记，则结果为n+1。因为未出现的最小正整数必然在1到n+1之间。
（2）算法实现（C语言）：
int findMissingPositive(int A[], int n) {
int i, j, a;
int B[n];
// 手动初始化数组
for (j = 0; j < n; j++) {
B[j] = 0;
}
// 标记存在的正整数
for (i = 0; i < n; i++) {
if (A[i] > 0 && A[i] <= n) {
a = A[i];
B[a - 1] = 1;
}
}
// 寻找第一个未标记的位置
for (i = 0; i < n; i++) {
if (B[i] == 0) break;
}
return i + 1;
}关键注释：标记数组B用于记录1到n的出现情况，遍历A标记有效值，遍历B找首个未标记项，索引加1得结果。
（3）复杂度分析：
- 时间复杂度：O(n)，其中遍历A和B各一次，每次操作为O(1)。
- 空间复杂度：O(n)，额外使用标记数组B，大小为n。