leetcode 352. Data Stream as Disjoint Intervals 区间合并

拼搏现实的明天。 2022-06-07 01:16 113阅读 0赞

Given a data stream input of non-negative integers a1, a2, …, an, …, summarize the numbers seen so far as a list of disjoint intervals.

For example, suppose the integers from the data stream are 1, 3, 7, 2, 6, …, then the summary will be:

\[1, 1\]  
\[1, 1\], \[3, 3\]  
\[1, 1\], \[3, 3\], \[7, 7\]  
\[1, 3\], \[7, 7\]  
\[1, 3\], \[6, 7\]  
Follow up:  
What if there are lots of merges and the number of disjoint intervals are small compared to the data stream’s size?

这道题就是考察区间的并运算，要注意使用Java的TreeSet结构，这道题很值得学习。

代码如下：

import java.util.ArrayList;
    import java.util.Comparator;
    import java.util.Iterator;
    import java.util.List;
    import java.util.TreeSet;
    
    
    /*class Interval
    {
          int start;
          int end;
          Interval() { start = 0; end = 0; }
          Interval(int s, int e) { start = s; end = e; }
    }*/
    
    
    /*
     * 参考这道题
     * https://www.programcreek.com/2014/08/leetcode-data-stream-as-disjoint-intervals-java/
     * 本题最快捷的方法就是使用TreeSet等结构，这是第一次用，
     * */
    class SummaryRanges 
    {
        TreeSet<Interval> set=null;
        /** Initialize your data structure here. */
        public SummaryRanges() 
        {
            set=new TreeSet<>(new Comparator<Interval>() {
                @Override
                public int compare(Interval a, Interval b) {
                    return a.start-b.start;
                }
            });
        }
    
        public void addNum(int val) 
        {
            Interval one=new Interval(val, val);
            Interval floor=set.floor(one);
            //找到比自己小的最大元素
            if(floor!=null)
            {
                if(val<=floor.end)
                    return ;
                else if(val==floor.end+1)
                {
                    one.start=floor.start;
                    set.remove(floor);
                }
            }
    
            Interval ceil=set.ceiling(one);
            //找到比自己大的最小元素
            if(ceil!=null)
            {
                if(val==ceil.start)
                    return ;
                else if(val+1==ceil.start)
                {
                    one.end=ceil.end;
                    set.remove(ceil);
                }
            }
            set.add(one);
        }
    
        public List<Interval> getIntervals() 
        {
            List<Interval> res=new ArrayList<Interval>();
            Iterator<Interval> iter=set.iterator();
            while(iter.hasNext())
                res.add(iter.next());
            return res;
        }
    }
    
    /**
     * Your SummaryRanges object will be instantiated and called as such:
     * SummaryRanges obj = new SummaryRanges();
     * obj.addNum(val);
     * List<Interval> param_2 = obj.getIntervals();
     */

下面是C++的做法，主要就是遍历即可

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    
    /*
    struct Interval 
    {
        int start;
        int end;
        Interval() : start(0), end(0) {}
        Interval(int s, int e) : start(s), end(e) {}
    };
    */
    
    class SummaryRanges 
    {
    public:
        vector<Interval> v;
    
        /** Initialize your data structure here. */
        SummaryRanges() 
        {
    
        }
    
        void addNum(int val) 
        {
            Interval cur(val, val);
            vector<Interval> res;
            int pos = 0;
            for (auto a : v) 
            {
                if (cur.end + 1 < a.start)
                {
                    res.push_back(a);
                }
                else if (cur.start > a.end + 1)
                {
                    res.push_back(a);
                    ++pos;
                }
                else 
                {
                    cur.start = min(cur.start, a.start);
                    cur.end = max(cur.end, a.end);
                }
            }
            res.insert(res.begin() + pos, cur);
            v = res;
        }
    
        vector<Interval> getIntervals() 
        {
            return v;
        }
    
    };