方法一
给定一个含n(n>=1)个整数的数组,请设计一个在时间上尽可能高效的算法,找出数组中未出现的最小正整数。例如,数组{-5,3,2,3}中未出现的最小正整数是1;数组{1,2,3}中未出现的最小正整数是4。要求:
-
给出算法的基本设计思想。
-
根据设计思想,采用C或C++语言描述算法,关键之 处给出注释。
-
说明你所设计算法的时间复杂度和空间复杂度。
读完题目先找关键词,这里可以直接提取这样几个关键词
- 使用数组,求未出现的最小正整数
- 看到数组,是不是想到是否有序
- 时间+空间尽可能高效
暴力解:快速排序,然后扫描一遍数组
先对数组A快速排序得到升序序列,然后遍历数组找到第一个未出现的最小正整数。
void Qsort(int A[], L, R){ //a数组保存数据,L和R是边界if (L>=R) return; //当前区间元素个数<=1则退出int key, i=L, j=R; //i和j是左右两个数组下标移动//把a数组中随机一个元素和A[L]交换,快排优化,使得基准值的选取随机key=A[L]; //key作为枢值参与比较while (i<j){while (i<j && A[j]>key) j--;while (i<j && A[i]<=key) i++;if (i<j) swap(A[i], A[j]); //交换A[i]和A[j]}swap(A[L], A[i]);Qsort(A, L, i-1); //递归处理左区间Qsort(A, i+1, R); //递归处理右区间}void ans(int A[], n){ //算法代码Qsort(A, 0, n-1);int i=0;while (i<n && A[i]<=0) i++;if (i==n){ //数组A全是非正数cout<<1;//输出1 return;}/*到这里,A[i]是数组中最小的正数*/ int t=1;//t从1开始for (int j=i; j<n; j++){ if (t==A[j])continue; if (t+1==A[j])t++;else{ //t+1空缺cout<<t+1; //输出j-i+1 return;}cout<<t+1;//遍历完数组,输出t+1}
}
方法二
解析:
思想借鉴到了 Counting sort 中的方法。既然不能用额外空间,那就只有利用
数组本身,跟 Counting sort 一样,利用数组的 index 来作为数字本身的索引,把正
数按照递增顺序依次放到数组中。即让 A[0]=1, A[1]=2, A[2]=3, … , 这样一来,
最后如果哪个数组元素违反了 A[i]=i+1 即说明 i+1 就是我们要求的第一个缺失的正
数。对于那些不在范围内的数字,我们可以直接跳过,比如说负数,0,或者超过数组
长度的正数,这些都不会是我们的答案。
思路:
交换数组元素,使得数组中第 i 位存放数值(i+1)。最后遍历数组,寻找第一
个不符合此要求的元素,返回其下标。整个过程需要遍历两次数组,复杂度为 O(n)。
下图以题目中给出的第二个例子为例,讲解操作过程。
public int firstMissingPositive(int []A){if(A==null||A.length==0){return 1;}for(int i=0;i<A.length;i++){if(A[i]<=A.length && A[i]>0 && A[A[i]-1]!=A[i]){int temp = A[A[i]-1];A[A[i]-1] = A[i];A[i] = temp;i--;}}for(int i=0;i<A.length;i++){it(A[i]!=i+1)return i+1;}return A.length+1;
}
实现中还需要注意一个细节,就是如果当前的数字所对应的下标已经是对应数字了,
那么我们也需要跳过,因为那个位置的数字已经满足要求了,否则会出现一直来回交
换的死循环。这样一来我们只需要扫描数组两遍,时间复杂度是 O(2*n)=O(n),而且
利用数组本身空间,只需要一个额外变量,所以空间复杂度是 O(1)。
补充
Counting sort 基本思想:
对于给定的输入序列中的每一个元素 x,确定该序列中值小于 x 的元素的个数 。一
旦有了这个信息,就可以将 x 直接存放到最终的输出序列的正确位置上。它创建一个
长度为这个数据范围的数组 C,C 中每个元素记录要排序数组中对应记录的出现个
数。
下面以示例来说明这个算法:
假设要排序的数组为 A = {1,0,3,1,0,1,1}这里最大值为 3,最小值为 0,那么我们
创建一个数组 C,长度为 4。
然后一趟扫描数组 A,得到 A 中各个元素的总数,并保持到数组 C 的对应单元中。比如 0 的出现次数为 2 次,则 C[0] = 2;1 的出现次数为4 次,则 C[1] = 4。由于 C 是以 A 的元素为下标的,所以这样一做,A 中的元素在 C中自然就成为有序的了,这里我们可以知道 顺序为 0,1,3 (2 的计数为 0)然后我们把这个在 C 中的记录按每个元素的计数展开到输出数组 B 中,排序就完成了。
也就是 B[0] 到 B[1] 为 0 B[2] 到 B[5] 为 1 这样依此类推。
这种排序算法,依靠一个辅助数组来实现,不基于比较,算法复杂度为 O(n) ,但由
于要一个辅助数组 C,所以空间复杂度要大一些,由于计算机的内存有限,所以这种
算法不适合范围很大的数的排序。
上述为计数排序算法的经典解法,不过这个解法并不是最优的,因为空间复杂度还应
该可以优化,我们完全可以不要那个输出的数组 B,直接对 C 进行排序。