首页 > 试题广场 >

牛牛的和平年代

[编程题]牛牛的和平年代
  • 热度指数:1159 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
题目背景:
数轴世界建立之初,还没有任何的生机。直到有一天,在数轴的整点上,慢慢诞生了一个一个新兴的文明。如果两个文明相邻,也就是在他们之间不存在其他的整点,他们就会慢慢受到彼此的影响,逐渐融为一个整体。而当所有的文明大一统,全部融为一个整体的时候,这个数轴世界才会重归和平。为了能够让自己的文明发展壮大,牛牛决定根据每个文明诞生的年代表,计算出什么时候才是和平的黄金时代。

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

示例1

输入

[3,5,4,6]

输出

[true,false,true,true]

说明

第一个前缀只有一个元素3,按照好的集合的定义,它显然是连续的。
第二个前缀有一个3和一个5,位于3和5之间的元素4却不在集合中,所以它不是连续的。
第三个前缀添加了一个4,弥补了第二个集合缺少4的问题,所以它是好的。
第四个前缀新增了一个6,依旧连续。

备注:
对于所有的数据,满足mSet的大小小于105, mSet[i]是32位有符号整数范围内的元素。
#include <unordered_map>
class Solution {
public:
    /**
     * 检查数组的每个前缀是不是一个好的集合
     * @param mSet int整型vector 
     * @return bool布尔型vector
     */
    vector<bool> continuousSet(vector<int>& mSet) {
        vector<bool> r;
        unordered_map<int, int> M;
        int Max=mSet[0], Min=mSet[0];
        for(auto &x: mSet){
            if(x > Max)
                Max = x;
            else if(x < Min)
                Min = x;
            M[x]++;
            if(Max-Min+1 == M.size())
                r.push_back(true);
            else
                r.push_back(false);
        }
        return r;
    }
};

发表于 2020-08-21 13:14:02 回复(0)
遍历数组,记录数组最大值,最小值,遍历下标,用一个hashmap记录重复值及个数,根据题意,有,最大值-最小值+1=遍历下标+1-重复值个数(比如有两个3重复值个数就是1) 这是目前思路,先记录下
发表于 2020-07-10 16:25:55 回复(0)