Very Short Java code with ArrayList and Binary Search


  • 0
    I
    public class SummaryRanges {
    
        List<Interval> list ;
        /** Initialize your data structure here. */
        public SummaryRanges() {
            list = new ArrayList();
        }
        
        public void addNum(int val) {
            insertInterval(val, list);
        }
        
        public List<Interval> getIntervals() {
            return new ArrayList(list);
        }
        
        private void insertInterval(int n, List<Interval> list) {
            if (list == null) return;
            if (list.size() == 0) {
                list.add(new Interval(n, n));
                return;
            }
            int start = 0; 
            int end = list.size() - 1;
            while (start + 1 < end) {
                int mid = start + (end - start) / 2;
                Interval midInterval = list.get(mid);
                if (midInterval.end >= n && midInterval.start <= n) return;
                if (midInterval.start > n) end = mid;
                else if (midInterval.end < n) start = mid;
            }
            
            Interval startInterval = list.get(start);
            Interval endInterval = list.get(end);
            
            // check different positions
            if (startInterval.start > n + 1) list.add(0, new Interval(n, n));
            else if (startInterval.start == n + 1) startInterval.start = n;
            else if (startInterval.end == n - 1) startInterval.end = n;
            else if (startInterval.end > n - 1) return;
            else if (endInterval.start > n + 1) list.add(end, new Interval(n, n));
            else if (endInterval.start == n + 1) endInterval.start = n;
            else if (endInterval.end == n - 1) endInterval.end = n;
            else if (endInterval.end < n - 1)list.add(new Interval(n, n));
            
            if (start != end && startInterval.end >= endInterval.start - 1) {
                startInterval.end = Math.max(startInterval.end, endInterval.end);
                list.remove(end);
            }
        }
    }
    

Log in to reply
 

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