将数据流变为多个不想交区间

将数据流变为多个不想交区间

 

 

变量简洁正确完整思路
map<int左边界,int右边界>left2right
map<Int右边界,int左边界>right2left
可以利用右边界查找左边界,可以利用左边界查找右边界
对于num,查找num-1作为右边界的左边界和num+1作为左边界的右边界
如果都有,新的左边界right2left[num-1]   新的右边界left2rightleft2right[num+1]
删掉原来的,
如果有左边界
如果有右边界
如果都没有

输出,因为map是排序的所以非常容易
class SummaryRanges {
public:
    map<int,int>left2right,right2left;
    /** Initialize your data structure here. */
    SummaryRanges() {

    }
    
    void addNum(int val) {
        auto iter=right2left.lower_bound(val);
        if(iter!=right2left.end()&&iter->second<=val)return;
        int hasLeft=right2left.count(val-1);
        int hasRight=left2right.count(val+1);
        if(hasLeft==1&&hasRight==1){
            int left=right2left[val-1];
            int right=left2right[val+1];
            //cout<<left<<‘ ‘<<right<<‘ ‘<<val<<endl;
            right2left.erase(val-1);
            left2right.erase(val+1);
            right2left[right]=left;
            left2right[left]=right;
            //cout<<right2left[val+1]<<‘ ‘<<val+1<<endl;
            //cout<<left<<‘ ‘<<left2right[val-1]<<endl;
        }
        else if(hasLeft==1&&hasRight==0){
            int left=right2left[val-1];
            //cout<<left<<‘ ‘<<val<<endl;
            right2left.erase(val-1);
            left2right.erase(left);
            right2left[val]=left;
            left2right[left]=val;
        }
        else if(hasLeft==0&&hasRight==1){
            int right=left2right[val+1];
            right2left.erase(right);
            left2right.erase(val+1);
            right2left[right]=val;
            left2right[val]=right;
        }else if(hasLeft==0&&hasRight==0){
            left2right[val]=val;
            right2left[val]=val;
        }
    }
    
    vector<vector<int>> getIntervals() {
        vector<vector<int>>ans;
        for(auto &mPair:left2right){
            ans.push_back({mPair.first,mPair.second});
        }
        return ans;
    }
};

/**
 * Your SummaryRanges object will be instantiated and called as such:
 * SummaryRanges* obj = new SummaryRanges();
 * obj->addNum(val);
 * vector<vector<int>> param_2 = obj->getIntervals();
 */
踩过的坑
            right2left[right]=left;
            left2right[left]=right;
            //right2left.insert({right,left});
            //left2right.insert({left,right});
不能用insert插入,因为这是映射关系,直接给一个数组会看做两次插入,map不需要
使用insert

如果已经有了,就直接跳过,比如[8,6],来了6,用lower_bound找到第一个大于等于
6,second小于等于6就跳过

lower_bound是大于等于,upper_bound是大于,没有任何小于

 

将数据流变为多个不想交区间

上一篇:(一)Pytorch处理VOC数据集以及dataset代码的编写


下一篇:替换所有换行符和2个以上的字符空格