给定一个含 n(n≥1)个整数的数组， 请设计一个在时间上尽可能高效的算法， 找出数组中未出现的最小正整数。 例如,数组{-5, 3, 2, 3}中未出现的最小正整数是 1； 数组{1, 2, 3}中未出现的最小正整数是 4。 要求：
给出算法的基本设计思想。
题目要求算法时间上尽可能高效， 因此采用空间换时间的办法。 分配一个用于标记的数组 B[n]， 用来记录 A 中是否出现了 1~n 中的正整数， B[0]对应正整数 1， B[n-1]对应正整数 n， 初始化 B 中全部为 0。 由于 A 中含有 n 个整数， 因此可能返回的值是 1~n+1， 当 A 中 n 个数恰好为1~n 时返回 n+1。 当数组 A 中出现了小于等于 0 或者大于 n 的值时， 会导致 1~n 中出现空余位置，返回结果必然在 1~n 中， 因此对于 A 中出现了小于等于 0 或者大于 n 的值可以不采取任何操作。
经过以上分析可以得出算法流程： 从 A[0]开始遍历 A， 若 0<A[i]<=n， 则令 B[A[i]-1]=1； 否则不做操作。 对 A 遍历结束后， 开始遍历数组 B， 若能查找到第一个满足 B[i]==0 的下标 i， 返回i+1 即为结果， 此时说明 A 中未出现的最小正整数在 1~n 之间。 若 B[i]全部不为 0， 返回 i+1（跳出循环时 i=n， i+1 等于 n+1）， 此时说明 A 中未出现的最小正整数是 n+1。
根据设计思想， 采用 C 或 C++语言描述算法， 关键之处给出注释。
int findMissMin(int A[] , int n)
{
int i, *B; //标记数组
B=(int *) malloc(sizeof(int) *n) ; //分配空间
memset(B, 0, sizeof(int) *n) ; //赋初值为0
for(i=0; i<n; i++)
if(A[i] >0&&A[i] <=n) //若A[i] 的值介于1~n， 则标记数组B
B[A[i] -1] =1;
for(i=0; i<n; i++) //扫描数组B， 找到目标值
if (B[i] ==0) break;
return i+1; //返回结果
}
说明你所设计算法的时间复杂度和空间复杂度。
时间复杂度： 遍历 A 一次， 遍历 B 一次， 两次循环内操作步骤为 O(1)量级， 因此时间复杂度为 O(n)。 空间复杂度： 额外分配了 B[n]， 空间复杂度为 O(n)。