题解 | #牛牛的和平年代#

牛牛的和平年代

http://www.nowcoder.com/practice/f60ad5b5594f4ad2ae1ee35d6e9e8f11

牛牛的和平年代

问题描述

我们定义一个整数可重集合是好的，当且仅当对于集合中任意两个元素 a, b ( $a \leq b$ ) ，所有满足 $a\leq c\leq b$ 的元素 c 都在集合中出现过。

现在，给你一个数组 mSet，你需要做的是，对于这个数组的每一个前缀，判断这个前缀是不是一个好的集合。所以，你将计算出的是一个数组，为布尔类型。

示例

输入：[3,5,4,6]

返回值：[true,false,true,true]

说明：第一个前缀只有一个元素3，按照好的集合的定义，它显然是连续的。
第二个前缀有一个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(\sum_{i=1}^{i=n}{i*i* \log i})$
空间复杂度：借助于一个辅助数组存储前缀元素，空间复杂度为$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)$