题解 | #牛牛的和平年代#
牛牛的和平年代
http://www.nowcoder.com/practice/f60ad5b5594f4ad2ae1ee35d6e9e8f11
牛牛的和平年代
问题描述
我们定义一个整数可重集合是好的，当且仅当对于集合中任意两个元素 a, b ( 现在，给你一个数组 mSet，你需要做的是，对于这个数组的每一个前缀，判断这个前缀是不是一个好的集合。所以，你将计算出的是一个数组，为布尔类型。
示例
输入：[3,5,4,6]
返回值：[true,false,true,true]
说明：第一个前缀只有一个元素3，按照好的集合的定义，它显然是连续的。
第二个前缀有一个3和一个5，位于3和5之间的元素4却不在集合中，所以它不是连续的。
第三个前缀添加了一个4，弥补了第二个集合缺少4的问题，所以它是好的。
第四个前缀新增了一个6，依旧连续。
第二个前缀有一个3和一个5，位于3和5之间的元素4却不在集合中，所以它不是连续的。
第三个前缀添加了一个4，弥补了第二个集合缺少4的问题，所以它是好的。
第四个前缀新增了一个6，依旧连续。
方法一
思路分析
设置一个数组，，每次添加一个元素进去构成该位置下的前缀，然后对前缀数组元素进行排序，如果两个前后的数不同而且相差不为1，那么可以判断前缀不连续，否则表示该位置下的前缀连续，不断的添加新元素到前缀数组中，直到添加完所有的元素。
图解
C++核心代码
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 检查数组的每个前缀是不是一个好的集合
* @param mSet int整型vector
* @return bool布尔型vector
*/
vector<bool> continuousSet(vector<int>& mSet) {
// write code here
int n=mSet.size();
vector<bool> res(n,false);
if (n==0) return res;
vector<int> array;
for(int i=0;i<n;i++)
{
array.push_back(mSet[i]);//每次将一个元素放入array
sort(array.begin(),array.end());//对前缀排序
int ans=0;
int nn=array.size();
for(int j=1;j<nn;j++)
{
if(array[j]-array[j-1]!=1&&array[j]!=array[j-1])
{////对排序的前缀判断是否连续，如果两个前后的数不同而且相差不为1，那么可以判断前缀不连续
res[i]=false;
ans=1;
}
}
if(ans==0) res[i]=true;
}
return res;
}
}; 复杂度分析 - 时间复杂度：首先循环遍历给定数组，每次添加一个元素进行排序，时间复杂度为$O(n \log n)$，每次排序后的比较次数为n次，总的时间复杂度为
- 空间复杂度：借助于一个辅助数组存储前缀元素，空间复杂度为$O(n)$
方法二
思路分析
方法一中需要对添加元素后的前缀数组进行重新排序，而后对排序后的前缀元素进行比较，前后的元素如果不相同那么必须相差1，这其中对数组的排序与比较会花费较多的时间，因此将每次添加的数组元素存储到map结构中，并且记录到当前情况下的前缀中的最大值与最小值，如果到当前位置添加的不同元素个数等于最大值减去最小值加一，那么证明该位置下的前缀数组是连续的。
C++核心代码
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 检查数组的每个前缀是不是一个好的集合
* @param mSet int整型vector
* @return bool布尔型vector
*/
vector<bool> continuousSet(vector<int>& mSet) {
// write code here
int n=mSet.size();
vector<int> dp(n,0);//用于存储set(mSet[:i])的长度
vector<bool> res(n,false);
if (n==0) return res;
dp[0]=1;
for(int i=1;i<n;i++)
{
vector<int>::const_iterator First = mSet.begin();
vector<int>::const_iterator Second = mSet.begin() + i+1;
vector<int> a(First, Second);
dp[i]=count(a);
}
int set_min=mSet[0];
int set_max=mSet[0];
res[0]=true;
for(int i=1;i<n;i++)
{
set_min=min(set_min,mSet[i]);
set_max=max(set_max,mSet[i]);
if(set_max-set_min+1==dp[i])//前缀是否连续
res[i]=true;
else res[i]=false;
}
return res;
}
int count(vector<int>& a)
{
sort(a.begin(),a.end());//快速排序
int count = 1;//统计不重复元素数
for(int i = 1;i<a.size();i++) {//第一个元素必然要计数
if(a[i]!=a[i-1]) {//和前一个元素重复则不计数
count++;
}
}
return count;
}
}; 复杂度分析 - 时间复杂度：计算数组中从开始位置到不同位置下的不重复元素的个数，时间复杂度为$O(n^2 \log n)$，遍历数组元素时找到当前位置下的前缀元素中的最大值与最小值，因此时间复杂度为$O(n^2 \log n)$
- 空间复杂度：借助于一个大小为$n$的数组存储给定数组中开始位置到当前位置的不重复的元素个数，空间复杂度为$O(n)$
MiniMax成长空间 43人发布