题目
请设计一个高效算法，查找数组中未出现的最小正整数。
给定一个整数数组A和数组的大小n，请返回数组中未出现的最小正整数。保证数组大小小于等于500。
测试样例：[-1,2,3,4],4返回：1 解法
1.我的解法
和上一篇文章一样，同样使用桶排序去解题，通过使用最大值去建桶，如果存在这个正整数，则将下标为此数的桶标志为1，然后找出为0的桶，输出最小正整数，如果所有桶为空则输出1，如果所有桶满，则输出最大值加1。
import java.util.*;public class ArrayMex { public int findArrayMex(int[] A, int n) { // write code here int max = 0,flag = 0; for (int i = 0;i < A.length;i++){ if(A[i] > max){ max = A[i]; } } int[] arr = new int[max+1]; for(int i = 0;i < A.length;i++){ if(A[i] > 0){ arr[A[i]]++; } } for(int i = 1;i < arr.length;i++){ if(arr[i] == 0){ return i; } } return max + 1; }}
2.改进解法
不过查阅答案发现这种解法并非最佳，对空间造成一定程度的浪费，在建桶的步骤中，可以使用n作为桶的上限，因为以n作为上限，A[i]>n的结果可以舍弃，这种情况下， 如果1到n都出现那么最下的结果为n+1，如果1到n中有数没出现则为空的第一个桶，如果1没有出现 那么最小结果为1。下面是代码：
//链接：https://www.nowcoder.com/questionTerminal/9e7a6bcdbce74feb8013d252d76855da//来源：牛客网public int findArrayMex(int[] A, int n) { int[] res = new int[n]; for (int i = 0; i < n; i++) { if (A[i]>0&&A[i]<=n){ res[A[i]-1]=1; } } for (int i = 0; i < n; i++) { if (res[i]==0){ return i+1; } } return n+1; } ```