infrastructureDataStructure10

题目描述[原题链接][https://leetcode-cn.com/problems/data-stream-as-disjoint-intervals/]

给定一个非负整数的数据流输入 a1，a2，…，an，…，将到目前为止看到的数字总结为不相交的区间列表。

例如，假设数据流中的整数为 1，3，7，2，6，…，每次的总结为：

[1, 1]
[1, 1], [3, 3]
[1, 1], [3, 3], [7, 7]
[1, 3], [7, 7]
[1, 3], [6, 7]

进阶：
如果有很多合并，并且与数据流的大小相比，不相交区间的数量很小，该怎么办?

算法描述

分两部分处理，首先是添加整数的时候，需要添加完数据后还是有序的，我采用的是lower_bound()函数，即二分查找到比当前值小的最后一个数，将要添加的数val添加到向量中，最后实现添加完的数据都是有序的；第二部就是找到区间，通过两层循环实现，遍历向量，如果前后两个数值相差1，即vec[j]-vec[j-1]<=1跳过，否则，跳出循环，压入vec[j-1]，更新i的值i=j-1，将结果添加到结果集中，遍历完整个向量结束；

C++代码

class SummaryRanges {
public:
    vector<int> vec;
    /** Initialize your data structure here. */
    SummaryRanges() {
        
    }
    
    void addNum(int val) {
        if(vec.empty())
            vec.push_back(val);
        else vec.insert(lower_bound(vec.begin(),vec.end(),val),val);    
    }
    
    vector<vector<int>> getIntervals() {
        vector<vector<int>> ans;
        for(int i=0;i<vec.size();i++){
            vector<int> res ;
            res.push_back(vec[i]);
            int j;
            for(j=i+1;j<vec.size();j++){
                if(vec[j]-vec[j-1]<=1)continue;
                else break;
            }
            //if(j>=vec.size())ans[t++].push_back(vec[j-1]);
            res.push_back(vec[j-1]);
            ans.push_back(res);
            i = j-1;
        }
        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();
 */

Java代码

class SummaryRanges {

   List<int[]> list;
   Set<Integer> set;
    /** Initialize your data structure here. */
    public SummaryRanges() {
        list = new ArrayList<>();
        set = new HashSet();
    }
    
    public void addNum(int val) {
        if(set.contains(val)){
            return ;
        }
        set.add(val);
        for(int i=0;i<list.size();i++){
            if(list.get(i)[0]>val){
                if(list.get(i)[0] == val+1){
                    list.get(i)[0] = val;
                }else{
                    int[] o = new int[]{val,val};
                    list.add(i,o);
                }
                return ; 
            }
            if(list.get(i)[1]>val){
                return ;
            }
            if(list.get(i)[1] == val - 1){
                list.get(i)[1] = val;
                if(i<list.size()-1&&list.get(i+1)[0] == val+1){
                    list.get(i+1)[0] = list.get(i)[0];
                    list.remove(i);
                }
                return;
            }
        }
        if(list.size()>0&&list.get(list.size()-1)[1] == val-1){
                list.get(list.size()-1)[1] = val;
            }
            else {
                int[] o = new int[]{val,val};
                list.add(o);
            }

    }
    
    public int[][] getIntervals() {
        int[][] res = new int[list.size()][2];
        for(int i=0;i<list.size();i++){
            res[i] = list.get(i);
        }
        return res;
    }

    public int lowerBound(int[] nums,int l,int r,int t){
        while(r>l){
            int m = (l+r)/2;
            if(nums[m]>t)r = m;
            else l = m+1;
        }
        return l;
    }
}

/**
 * Your SummaryRanges object will be instantiated and called as such:
 * SummaryRanges obj = new SummaryRanges();
 * obj.addNum(val);
 * int[][] param_2 = obj.getIntervals();
 */