C++ using map O(LogN) insert and O(N) get


  • 0
    X
     class SummaryRanges {
        public:
            SummaryRanges() {
                
            }
            
            void addNum(int val) {
                if(m.find(val) != m.end()){
                    return;
                }
                m[val] = 1;
                auto left = m.find(val - 1);
                auto right = m.find(val + 1);
                if(left != m.end() && right != m.end()){
                    int leftnum = m[val - 1];
                    int rightnum = m[val + 1];
                    m[val - leftnum] = leftnum + rightnum + 1;
                    m[val + rightnum] = leftnum + rightnum + 1;
                    interval.erase(interval.find(val + 1));
                    interval[val - leftnum] = leftnum + rightnum + 1;
                }else if(left != m.end()){
                    int leftnum = m[val - 1];
                    m[val - leftnum] = leftnum + 1;
                    m[val] = leftnum + 1;
                    interval[val - leftnum] = leftnum + 1;
                }else if(right != m.end()){
                    int rightnum = m[val + 1];
                    m[val + rightnum] = rightnum + 1;
                    m[val] = rightnum + 1;
                    interval.erase(interval.find(val + 1));
                    interval[val] = rightnum + 1;
                }else{
                    interval[val] = 1;
                };
            }
            
            vector<Interval> getIntervals() {
                vector<Interval> ans;
                for(auto i = interval.begin(); i != interval.end(); ++i){
                    ans.push_back(Interval(i->first, i->first + i->second - 1));
                }
                return ans;
            }
        private:
            map<int, int, less<int>> interval;
            unordered_map<int, int> m;
        };

Log in to reply
 

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