Java, just use LinkedList, O(n) or O(log n)? per add, O(n) per get(with explanations).


  • 0
    Z

    Important : This method is no better than TreeSet/TreeMap and it's just for ur consideration.
    I use a sorted list to represent the intervals. And all test cases cost 200ms

    • Because the interval always contains start and end. The length of the list must be 2*n;
    • When add, It is easy to do the ops because it will only affect the previous and next intervals (and it correspond to the previous and next elements in the list), so u have to scan (O(n)) the list or use some search methods (maybe O(log n)) to get the location(In this code, I scan the list so when add, it is O(n);)
    • When get, just scan the list and make every 2 elements as an interval's start and end and it costs O(n) (because I do not maintain an object that can be directly returned, so it maybe have some additional cost in creating the return object)
    • Pardon my poor code style :(
    /**
     * Definition for an interval.
     * public class Interval {
     *     int start;
     *     int end;
     *     Interval() { start = 0; end = 0; }
     *     Interval(int s, int e) { start = s; end = e; }
     * }
     */
    public class SummaryRanges {
    
        List<Integer> list = new LinkedList<Integer>();
        /** Initialize your data structure here. */
        public SummaryRanges() {
            
        }
        
        public void addNum(int val) {
            if(list.size() == 0) {
                list.add(0, val);
                list.add(1, val);
                return;
            }
            for(int i =0; i < list.size(); i++){
                if(i%2 == 0){// means the begin of an interval
                    if(val == list.get(i) - 1){
                        list.set(i, val);
                        if(i != 0 && val <= list.get(i-1) + 1){//merge with previous interval
                            list.remove(i);
                            list.remove(i-1);
                        }
                        break;
                    }else{
                        if(val < list.get(i) - 1){
                            list.add(i, val);
                            list.add(i+1, val);
                            break;
                        }
                    }
                }else{// end of an interval
                    if(val == list.get(i) + 1){
                        list.set(i, val);
                        if(i+1 < list.size() && val >= list.get(i+1) - 1){//merge with next interval
                            list.remove(i);
                            list.remove(i);//notice: when u remove node i, the node i+1 will become node i
                        }
                        break;
                    }else{
                        if(val <= list.get(i)) break;
                        else if(i == list.size() - 1){
                            list.add(val);
                            list.add(val);
                            break;
                        }
                    }
                }   
            }
        }
        
        public List<Interval> getIntervals() {
            List<Interval> ret = new ArrayList<Interval>();
            for(int i = 0; i < list.size(); i+=2){
                Interval temp = new Interval(list.get(i), list.get(i+1));
                ret.add(temp);
            }
            return ret;
        }
    }
    
    /**
     * Your SummaryRanges object will be instantiated and called as such:
     * SummaryRanges obj = new SummaryRanges();
     * obj.addNum(val);
     * List<Interval> param_2 = obj.getIntervals();
     */
    

Log in to reply
 

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