408数据结构专项算法题-2018年

题目：

分析：类似于2年前的排序问题难度，要进行有思考的暴力，即找到一些题目隐含的性质。

注：如果只是贴正确思路的话非常简单，展示错误思路有利于我整理思考一道题目的过程，锻炼思维的循序渐进。

        

思路一：开标记数组（实现不了）

思考：开一个标记数组，用来标记哪些正整数已经出现，循环遍历标记数组没出现的即为最小的。这里有个很重要的问题，即标记数组应该开多大？我们为了方便表示记len为长度，len=n吗？显然不对，按照这种思路应该与数组中最大值有关，但要注意的是原数组是整数，包括了负整数。如果全为负数的话，那么最小正整数直接就是1。事情就这么结束了吗？不不不，我们还没讨论数组元素的取值范围呢，如果按照数学角度理解的话，这个空间根本是开不了的，任何电脑都开不了。如果是数据范围中的int，long long，所开空间复杂度也是个恐怖的量，只能开在堆上。暴力思路失败！开始思考优化，

思路二：双重循环

思考：上述的思路不行了，后面再审题发现一个重要性质，即最小正整数的取值一定是 1<=x<=n+1,不理解可以自己随便造几组数据理解一下。

#include <iostream>
using namespace std;
const int N=1e5;
int a[N],n;
int find_min(int a[],int n)
{
	for(int i=1;i<=n+1;i++)
	{
		int flag=0;
		for(int j=0;j<n;j++)
		{
			if(a[j]==i) 
			{
				flag=1;
				break;
			}
		}
		if(!flag) return i;//没出现的最小正整数 
	}
}
int main()
{
	cin>>n;
	for(int i=0;i<n;i++) cin>>a[i];
	cout<<find_min(a,n);
	return 0;
}

时间复杂度：O（n^2）,空间复杂度：O（1）

思路三：排序

思考：对数组进行排序后，能通过坐标更容易找到最小这个概念。

#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e5;
int a[N],n;
int find_min(int a[],int n)
{
	int i,j;//i指向数组中的数，j指向1到n+1
	for(i=0,j=1;i<n;i++)//双指针移动
	{
		if(a[i]>0)//只针对正整数
		{
			if(a[i]==j) j++;
			if(a[i]>j) return j;//找到最小正整数
		}
	}
	return j;//全部都连贯的情况下 如1 2 3 4，要补充一次返回
}
int main()
{
	cin>>n;
	for(int i=0;i<n;i++) cin>>a[i];
	sort(a,a+n);//排序
	cout<<find_min(a,n);
	return 0;
}

平均时间复杂度：O（nlogn），空间复杂度O（1）.

思路四：开空间再思考

思考：思路一开空间的思路无疾而终，在思路二中发现重要的性质1<=x<=n+1后，突然意识到这完美的限制了所开空间的大小即0-n。

#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e5;
int a[N],b[N],n;
int find_min(int a[],int n)
{
	for(int i=0;i<n;i++)
		if(a[i]<=n&&a[i]>0) b[a[i]]++;
	for(int i=1;i<=n;i++)
	{
		if(!b[i]) return i;
	}
	return n+1;//全部都连贯的情况下 如1 2 3 4
}
int main()
{
	cin>>n;
	for(int i=0;i<n;i++) cin>>a[i];
	cout<<find_min(a,n);
	return 0;
}

时间复杂度：O（n），空间复杂度O（n）