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

题目描述
我们定义一个整数可重集合是好的，当且仅当对于集合中任意两个元素 a, b (a≤b) ，所有满足 a≤c≤b 的元素 c 都在集合中出现过。
现在，给你一个数组 mSet，你需要做的是，对于这个数组的每一个前缀，判断这个前缀是不是一个好的集合。所以，你将计算出的是一个数组，为布尔类型。

方法一：暴力求解

求解思路
对于本题目的求解，我们首先对输入的数据定义一个数组，每次添加一个元素进去构成该位置的前缀。然后对数组进行排序，如果前后两个数不同，而且不相差1，那么可以得知这个位置是不连续的，否则为连续的。按照上述的思路，对输入进行遍历，最后即可求出相应的答案。

图片说明

解题代码

class Solution {
public:
    vector<bool> continuousSet(vector<int>& mSet)
    {
        int n = mSet.size(); // 存储mset的大小
        vector<bool> myres(n,false); // 存储结果
        if (n==0) return myres; // 直接返回结果
        vector<int> temp;
        for(int i=0;i<n;i++)
        {
            temp.push_back(mSet[i]);
            if(iscontinue(temp)) // 按照题目的思路进行判断
                myres[i]=true;
        }
      return myres; // 返回结果
    }
    bool iscontinue(vector<int> temp)
    {
         sort(temp.begin(),temp.end()); // 快排
         for(int m = 1;m <temp.size();m++)
         {
            if(temp[m] - temp[m - 1] != 1 &&temp[m] !=temp[m - 1])
            {
                return false; // 不连续，返回false
            }
        }
        return true; // 连续，返回true
    }
};

复杂度分析
时间复杂度：一层循环加快排，因此时间复杂度为 $O(NlogN)$
空间复杂度：使用数组temp[n],因此空间复杂度为 $O(N)$

方法二：优化思想求解

求解思路
基于方法一，我们发现每次添加输入的数值以后都要进行重新排序，因此我们对方法一进行优化，设置临时变量来存储当前数组的最大最小值，并且新加入元素后只对临时变量进行更新即可。然后其他思路同方法一，对辅助数组进行排序，进行相差1的判断，最后输出结果即可。

图片说明

解题代码

class Solution {
public:
    vector<bool> continuousSet(vector<int>& mSet)
    {
        int n=mSet.size(); // 存储mset的大小
        vector<bool> myres(n,false); // 存储大小
        if (n==0) return myres;
        map<int,int> temp;
        int mymin=mSet[0]; // 声明变量记录最小值
        int mymax=mSet[0]; // 声明变量记录最大值
        myres[0]=true;
        temp[mSet[0]]++;
        for(int i=1;i<n;i++)
        {
            mymin=min(mymin,mSet[i]); // 记录最小值
            mymax=max(mymax,mSet[i]); // 记录最大值
            temp[mSet[i]]++; // 更新临时变量
            if(mymax-mymin+1==temp.size())
                myres[i]=true;
            else myres[i]=false;
        }
      return myres; // 返回结果
    }
};

复杂度分析
时间复杂度：一层循环，因此时间复杂度为 $O(N)$
空间复杂度：使用map型的temp,因此空间复杂度为 $O(N)$