数据结构笔记12：在含n个整数的数组中找未出现的最小正整数

【2018年408统考真题】

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

1、第一种方法（暴力搜寻）

算法思想：
最小正整数是1，从1开始增加，每个正整数都在数组中找是否有这个数，没有则输出

算法时间复杂度是O(n^2)，空间复杂度O(n)

代码实现

#include"head.h";
int FindMissMin1( int a[], int length){
	int i;
	int n=1;
	for (i = 0; i < length; i++)
	{
		if (a[i] == n)
		{
			n++;
			return FindMissMin1(n, a, length);//相当于再一次执行函数
		}
	}
	return n;
}

int main()
{
	int a[100];//初始数组长度
	printf("请输入数组的长度:\n");
	int length;
	scanf_s("%d", &length);
	printf("请输入数组元素:\n");
	int i;
	for (i = 0; i < length; i++)
	{
		scanf_s("%d", &a[i]);
	}

	printf("未出现的最小正整数为:\n");
	int min = FindMissMin1( a, length);
	printf("%d\n", min);

	system("pause");
	return 0;
}

2、第二种方法（先排序后判断）

算法思想：
在第一种方法的基础上对时间复杂度进行优化，先将数组进行排序，再进行循环判断，此处可以使用时间复杂度O(nlog2n)的快速排序，也可以使用时间复杂度为O(n)的基数排序。

快速排序
算法时间复杂度为O(nlog2n)，空间复杂度O(n)

基数排序
算法时间复杂度为O(n)，空间复杂度O(10n)

注：此处使用快速排序方法，因为小编不会基数排序，略微有点尴尬

代码实现

#include"head.h";

//快速排序（从小到大）
void quickSort(int s[], int l, int r)
{
	if (l < r)
	{
		int i = l, j = r, x = s[l];
		while (i < j)
		{
			while (i < j && s[j] >= x) // 从右向左找第一个小于x的数
				j--;
			if (i < j)
				s[i++] = s[j];
			while (i < j && s[i] < x) // 从左向右找第一个大于等于x的数
				i++;
			if (i < j)
				s[j--] = s[i];
		}
		s[i] = x;
		quickSort(s, l, i - 1); // 递归调用
		quickSort(s, i + 1, r);
	}
}

int FindMissMin2(int a[], int length) {
	int n = 1;
	//将原数组中大于0的数放在新数组中，在新数组中判断未出现的最小正整数。
	//这样可以排除原数组中负数的影响
	int b[100];
	int i = 0, j = 0;
	for ( ; i < length; i++) {
		if (a[i] > 0) {
			b[j] = a[i];
			j++;
		}
	}
	//遍历只有正整数的新数组，判断未出现的最小正整数
	for (int i = 0; i < j; i++)
	{
		if (b[i]>n)
		{
			return n;
		}
		n++;
	}
	return n;
}

int main()
{
	int a[100];//初始数组长度
	printf("请输入数组的长度:\n");
	int length;
	scanf_s("%d", &length);
	printf("请输入数组元素:\n");
	int i;
	for (i = 0; i < length; i++)
	{
		scanf_s("%d", &a[i]);
	}
	quickSort(a, 0, length-1);
	printf("未出现的最小正整数为:\n");
	int min = FindMissMin2( a, length);
	printf("%d\n", min);
	system("pause");
	return 0;
}

3、第三种方法（第二种方法在时间上再优化）

算法思想：

从头开始遍历数组a,将数组a中大于0小于n的数在数组b用b[a[i]-1]中标记，对a遍历结束后，开始遍历数组b，第一个满足b[i]=0的数的下标即为输出结果。
找几个数在纸上换算一下数组a和数组b的关系，就很容易理解这种算法。

算法时间复杂度度O(n)，空间复杂度O(n)

代码实现

#include"head.h"
int FindMissMin3(int a[], int n) {
	int i, *b;
	b = (int *)malloc(sizeof(int) * n);//给数组b分配空间
	memset(b, 0, sizeof(int) * n);//将数组b中所有值初始化为0
	for (i = 0; i < n; i++) {
		if (a[i] > 0 && a[i] <= n)
		{
			b[a[i] - 1] = 1;//若a[i]的值介于1-n之间，则标记数组b
		}
	}
	for (i = 0; i < n; i++){
		if (b[i]==0)
		{
			break;//扫描数组b，第一个为0的数便为数组a中未出现的最小正整数,找到后跳出当前循环
		}
	}
	return i + 1;//i+1可理解为数组b中从1开始递增的正整数，数组b中的元素为0时，i+1则为数组b的最小正整数
}
int main()
{
	int *a;//初始数组长度

	printf("请输入数组的长度:\n");
	int n;
	scanf_s("%d", &n);
	a = (int*)malloc(sizeof(int) * n);
	memset(a, 0, sizeof(int) * n);
	printf("请输入数组元素:\n");
	int i;
	for (i = 0; i < n; i++)
	{
		scanf_s("%d", &a[i]);
	}
	printf("未出现的最小正整数为:\n");
	int min = FindMissMin3(a, n);
	printf("%d\n", min);
	system("pause");
	return 0;
}

输出测试

a[]={-1,2,3,4,5}

未出现最小正整数为：1

4、总结

1. 此题涉及到的方法有“穷举搜索法”和“快速排序法”以及空间换时间的思想。
2. 如果想不到好的方法就选择暴力搜索，一项一项比对。
3. 第二种方法在判断的时候还可以利用二分法在时间上对算法再优化。
4. 第三种方法可以再在空间上优化，使空间复杂度为O(1)，因为此题不用再涉及，故没在继续深究。
5. 每个问题都有很多种不同的算法，欢迎大家在评论区一起讨论更好的方法。