2021.10.9打卡

个人思路：模拟插入

使用vector存储插入的数字。addNum使用二分查找插入，getIntervals遍历数组，temp数组存储连续数字，如果当前值是之前值+1，那么插入temp，否则生成临时数组{temp.front(),temp.back()},插入结果数组，然后清空数组temp继续遍历。

class SummaryRanges {
public:
    SummaryRanges() {

    }
    
    void addNum(int val) {
        if(nums.empty()){
            nums.push_back(val);
            return;
        }
        int left=0,right=nums.size()-1;
        while(left<=right){
            int mid=left+right>>1;
            if(nums[mid]val)
                right=mid-1;
            else
                return;
        }
        nums.insert(nums.begin()+left,val);
    }
    
    vector> getIntervals() {
        vector> res;
        vector temp;
        if(nums.empty())
            return res;
        temp.push_back(nums[0]);
        for(int i=1;i t={temp.front(),temp.back()};
                res.emplace_back(t);
                temp.clear();
                temp.push_back(nums[i]);
            }
        }
        if(temp.size()){
            vector t={temp.front(),temp.back()};
            res.emplace_back(t);
            temp.clear();
        }
        return res;
    }

    vector nums;
};

优化思路：使用有序映射维护区间

情况一：存在区间[l,r], 完全包含val，那么加入val之后，区间集合不会有任何变化

情况二：存在区间[l,r], 右区间r紧贴val，即r+1==val, 加入val后，区间从[l,r]变为[l,r+1]

情况三：存在区间[l,r], 它的左区间紧贴val，即l-1==val, 加入val后，区间从[l,r]变为[l-1,r]

情况四：情况二和三同时满足，即存在一个区间[L0,R0]，满足R0+1val,并且存在一个区间[L1,R1]满足L1-1val，则将两个区间合并成大区间。

情况五：上述四种情况都不满足，val单独形成一个区间[val,val]

class SummaryRanges {
public:
    map intervals;

    SummaryRanges() {
    }
    
    void addNum(int val) {
        auto it1=intervals.upper_bound(val);
        auto it0=(it1==intervals.begin()?intervals.end():prev(it1));
        if(it0!=intervals.end()&&it0->first<=val&&val<=it0->second)
            return;
        bool left_side=(it0!=intervals.end()&&it0->second+1==val);
        bool right_side=(it1!=intervals.end()&&it1->first-1==val);
        if(left_side&&right_side){
            int left=it0->first;
            int right=it1->second;
            intervals.erase(it0->first);
            intervals.erase(it1->first);
            intervals.emplace(left,right);
        }
        else if(left_side){
            ++it0->second;
        }
        else if(right_side){
            int right=it1->second;
            intervals.erase(it1->first);
            intervals.emplace(val,right);
        }
        else{
            intervals.emplace(val,val);
        }
    }
    
    vector> getIntervals() {
        vector> res;
        for(auto& it:intervals){
            vector temp={it.first,it.second};
            res.push_back(temp);
        }
        return res;
    }
};

• 时间复杂度
  • addNum O(logn)
  • getIntervals O(n)
• 空间复杂度 O(n)