给定一个含n(n≥1)个整数的数组，请设计一个在时间上

第1题

给定一个含n(n≥1)个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数。例如,数组{-5, 3, 2, 3}中未出现的最小正整数是1；数组{1, 2, 3}中未出现的最小正整数是4。要求：

（1）给出算法的基本设计思想。

（2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。

（3）说明你所设计算法的时间复杂度和空间复杂度。

答：（1）题目要求算法时间上尽可能高效，因此采用空间换时间的办法。分配一个用于标记的数组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。

（2）

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;//返回结果
}

（3）时间复杂度：遍历A一次，遍历B一次，两次循环内操作步骤为O(1)量级，因此时间复杂度为O(n)。空间复杂度：额外分配了B[n]，空间复杂度为O(n)。