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

牛牛的和平年代

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

思路:

题目的主要信息(直接看题意,背景不重要):

  • 对于数组mSet,每次以前个元素为一个集合,如果集合中出现了最小数到最大数中的所有元素,则返回true,否则返回false
  • 需要判断每一个前缀是否为true,第一个元素一定是true

方法一:排序+暴力解法
具体做法:
遍历数组mSet,每次将新元素加入辅助数组,然后对辅助数组进行排序,排成递增序。然后遍历辅助数组,如果出现前后两个数相差大于1,则一定为false,遇到相差为1的元素,计数器加一,最后如果计数器等于尾元素减首元素说明填满了这其中所有的元素,是返回true。

class Solution {
public:
    vector<bool> continuousSet(vector<int>& mSet) {
        vector<bool> res;
        vector<int> temp; //临时数组,每次记录到i的长度的mSet数组
        if(mSet.size() == 0)
            return res;
        res.push_back(true); //第一个一定为true
        temp.push_back(mSet[0]);
        for(int i = 1; i < mSet.size(); i++){
            temp.push_back(mSet[i]); //加入当前元素后排序
            sort(temp.begin(), temp.end());
            int gap = 0;
            for(int j = 1; j < temp.size(); j++){
                if(temp[j] - temp[j - 1] > 1){ //差距大于1,说明有间隔元素
                    res.push_back(false);
                    break;
                }
                if(temp[j] != temp[j - 1]) //这里是相差为1
                    gap++;
            }
            if(gap == temp[temp.size() - 1] - temp[0]) //相差刚好是尾减去首,说明填满
                res.push_back(true);
        }
        return res;
    }
};

复杂度分析:

  • 时间复杂度:,完整的复杂度应该是,省略了低次幂
  • 空间复杂度:,辅助数组temp,res是必要空间,不属于额外空间

方法二:哈希表
具体做法:
我们想要知道的是每次前缀的最大元素和最小元素之间是否被填满了,如果前缀中不同的元素一共有个,那么就一定填满,否则不行。因此我们可以想到用哈希表统计每个元素出现的次数,哈希表的大小就是不同元素的个数。
图片说明

class Solution {
public:
    vector<bool> continuousSet(vector<int>& mSet) {
        vector<bool> res;
        unordered_map<int, int> mp; //哈希表记录重复数组,即出现了多少不同的数字
        int maxnum = mSet[0];
        int minnum = mSet[0];
        for(int i = 0; i < mSet.size(); i++){
            maxnum = max(maxnum, mSet[i]); //更新最大值最小值
            minnum = min(minnum, mSet[i]);
            mp[mSet[i]]++;
            if(maxnum - minnum + 1 == mp.size()) //哈希表中的元素刚好填满最大值到最小值
                res.push_back(true);
            else
                res.push_back(false);
        }
        return res;
    }
};

复杂度分析:

  • 时间复杂度:,遍历一次数组,为数组长度
  • 空间复杂度:,最坏情况下所有元素都不同,哈希表大小为
孤帆远影碧空尽 文章被收录于专栏

牛客网各类题单题解~

全部评论

相关推荐

06-17 00:26
门头沟学院 Java
程序员小白条:建议换下项目,智能 AI 旅游推荐平台:https://github.com/luoye6/vue3_tourism_frontend 智能 AI 校园二手交易平台:https://github.com/luoye6/vue3_trade_frontend GPT 智能图书馆:https://github.com/luoye6/Vue_BookManageSystem 选项目要选自己能掌握的,然后最好能自己拓展的,分布式这种尽量别去写,不然你只能背八股文了,另外实习的话要多投,尤其是学历不利的情况下,多找几段实习,最好公司title大一点的
无实习如何秋招上岸
点赞 评论 收藏
分享
06-28 22:48
已编辑
广东金融学院 Java
小浪_Coding:学院本+这俩项目不是buff叠满了嘛
点赞 评论 收藏
分享
评论
2
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务