题目

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

题解

分析

遍历A数组，利用辅助动态数组，类似之前提到过的，元素值作为数组下标。第一个为0的值即是所求的最小正整数。

代码

int findmin(int A[], int n){int *B = (int *)malloc(sizeof(int) * n);for(int i=0;i<n;i++)B[i]=0;for(int i=0;i<n;i++){if(A[i]>0 && A[i]<n)B[A[i]-1]++;}for(int i=0;i<n;i++)if(B[i]==0)break;return i+1;
}