Easy solution using one Set in C++, O(logN) for insert, but O(N) for getIntervals


  • 0
    L

    Actually I am looking for some O(1) for getInterval with O(logN) for add, but it looks not so straight-forward, and perhaps during a 45 minutes interview it will be so hard to code out. Using a set will be much easier to write the code.

    set<int> tree; // binary search tree implemented by set, ordered
    /** Initialize your data structure here. */
    SummaryRanges() { }
    
    void addNum(int val) {		
    	tree.insert(val);
    }
    
    vector<Interval> getIntervals() {
    	// this will be about O(N), but very easy to get
    	vector<Interval> result;
    	bool isfirst = true;
    	int begin=0, end=0;
    	
    	for(int i : tree) {
    	    if(isfirst) {
    	        begin = i;
    	        end = i;
    	        isfirst = false;
    	    }
    	    else {
    	        if( i > end+1) {
    	            result.push_back(Interval(begin, end));
    	            begin = i;
    	            end = i;
    	        }
    	        else {
    	            end = i;
    	        }
    	    }
    	}
    	
    	// for last one
    	result.push_back(Interval(begin, end));
    	
    	return result;
    }

  • 0
    X

    I think have a cleaner solution for the same complexity that you are trying to achieve:

    class SummaryRanges {
        set<int>st;
    public:    
        void addNum(int val) {
            st.insert(val);
        }
        
        vector<Interval> getIntervals() {
            vector<Interval> result;
            for (auto num : st) {
                if (result.empty() || result.back().end + 1 != num)
                    result.emplace_back(num, num);
                else
                    result.back().end = num;
            }
            return result;       
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.