本文主要是介绍找出未出现的最小正整数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
给定一个含n(n≥1)个整数的数组，找出数组中未出现的最小正整数。例如，数组{-5, 3, 2, 3}中未出现的最小正整数是1；数组{1, 2, 3}中未出现的最小正整数是4。
方法一：
思想。对数组进行快速排序，然后进行遍历数组。
①第一个元素大于0，且不为1，则最后返回1；出现正数之前的元素为负数，且第一个正数不为1，则返回1。例如：-1，2,3；例如，2,3,4
②现的正整数之间差值大于1，且在此之前均为连续的数。例如：1,2,3,6；返回4
③全部为正数，且为连续正整数。例如：1 2 3 4.最后返回5
④全部为负数或最后为0。例如： -3，-2，0 返回1
int partition(int A[],int low,int high){int pivot=A[low];//选择第一个元素作为枢纽 while(low<high){while(low<high && A[high]>=pivot){--high;}A[low]=A[high]; //比枢纽小的元素移到左端 while(low <high && A[low]<= pivot){++low;}A[high]=A[low];//比枢纽大的元素移到右端 }A[low]=pivot;return low;
}
void quicksort(intA[],int low,int high){if(low<high){int pivotpos=partition(A,low,high);//第一次快排 quicksort(A,low,pivotpos-1);//左侧快排 quicksort(A,pivotpos+1,high);//右侧快排 }
}
int getMin(int A[],int n){quicksort(A,0,n-1);//进行快速排序 for(int i=0;i<n;i++){//第一个元素大于0，且不为1，则最后返回1；出现正数之前的元素为负数，且第一个正数不为1，则返回1。例如：-1，2,3；例如，2,3,4 if(A[0]>0&& A[0] !=1 || A[i]>0 && A[i-1]<0&& A[i] !=0){return 1;}else if(i>0&&A[i]>0&&A[i-1]>0&&A[i]-A[i-1]>1){//出现的正整数之间差值大于1，且在此之前均为连续的数。例如：1,2,3,6；返回4 return A[i-1]+1;}}if(A[n-1]>0){//全部为正数，且为连续正整数。例如：1 2 3 4.最后返回5 return A[n-1]+1;}else{//全部为负数或最后为0。例如： -3，-2，0 返回1 return 1;}
}
时间复杂度O（logn）；空间复杂度O（logn）
方法二：
明天再更。。。
这篇关于找出未出现的最小正整数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
