本文共 7405 字，大约阅读时间需要 24 分钟。
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?跟 是一个类型的题目
input变了，根据答案改写的
class SummaryRanges { TreeMap tree; /** Initialize your data structure here. */ public SummaryRanges() { tree = new TreeMap (); } public void addNum(int val) { if(tree.containsKey(val)) return; Integer low = tree.lowerKey(val); Integer high = tree.higherKey(val); if(low != null && high != null && val == tree.get(low)[1]+1 && val == tree.get(high)[0]-1){ tree.get(low)[1] = tree.get(high)[1]; tree.remove(high); tree.put(low, tree.get(low)); } else if(low != null && val <= tree.get(low)[1]+1){ tree.get(low)[1] = Math.max(val, tree.get(low)[1]); tree.put(low, tree.get(low)); } else if(high != null && val >= tree.get(high)[0]-1){ tree.get(high)[0] = Math.min(val,tree.get(high)[0]); tree.put(high, tree.get(high)); } else { int[] arr = { val, val}; tree.put(val, arr); } } public int[][] getIntervals() { List list = new ArrayList<>(tree.values()); int[][] res = new int[list.size()][2]; for(int i = 0; i < list.size(); i++){ res[i] = list.get(i); } return res; }} leetcode solution 1: Using TreeMap
public class SummaryRanges { TreeMap tree; public SummaryRanges() { tree = new TreeMap<>(); } public void addNum(int val) { if(tree.containsKey(val)) return; Integer l = tree.lowerKey(val); Integer h = tree.higherKey(val); if(l != null && h != null && tree.get(l).end + 1 == val && h == val + 1) { tree.get(l).end = tree.get(h).end; tree.remove(h); } else if(l != null && tree.get(l).end + 1 >= val) { tree.get(l).end = Math.max(tree.get(l).end, val); } else if(h != null && h == val + 1) { tree.put(val, new Interval(val, tree.get(h).end)); tree.remove(h); } else { tree.put(val, new Interval(val, val)); } } public List getIntervals() { return new ArrayList<>(tree.values()); }} leetcode solution 2: UnionFind
因为这里只关注boarder，所以只需要找每个interval边界的root，比常规的UF更简单 最后输出用TreeSet解决Set无序的问题 效率不好，时间复杂度应该是nlogn吧，空间复杂度也很高class SummaryRanges { HashMap map; HashMap Intervals; /** Initialize your data structure here. */ public SummaryRanges() { map = new HashMap<>(); Intervals = new HashMap<>(); } public void addNum(int val) { if(map.containsKey(val)) return; else{ map.put(val,1); if(map.containsKey(val+1) && map.containsKey(val-1)){ int l = map.get(val+1); int r = map.get(val-1); map.put(val+l,l+r+1); map.put(val-r,l+r+1); Intervals.remove(val+1); Intervals.put(val-r,l+r+1); } else if(map.containsKey(val+1)){ int l = map.get(val+1); map.put(val+l,l+1); map.put(val,l+1); Intervals.remove(val+1); Intervals.put(val,l+1); } else if(map.containsKey(val-1)){ int r = map.get(val-1); map.put(val-r,r+1); map.put(val,r+1); Intervals.put(val-r,r+1); } else Intervals.put(val,1); } } public int[][] getIntervals() { int[][] res = new int[Intervals.size()][2]; int k = 0; Set set = new TreeSet<>(); for(Integer i: Intervals.keySet()){ set.add(i); } for(Integer i: set){ res[k][0] = i; res[k][1] = i+Intervals.get(i)-1; k++; } return res; }} leetcode solution 3: BST
记录一下，以后再看public class SummaryRanges { class BSTNode { Interval interval; BSTNode left; BSTNode right; BSTNode(Interval in){ interval = in; } } BSTNode findMin(BSTNode root) { if (root == null) return null; if (root.left == null ) return root; else return findMin(root.left); } BSTNode remove(Interval x, BSTNode root) { if (root == null) return null; else if ( x == null ) return root; else if (x.start > root.interval.end ) { root.right = remove(x, root.right); } else if (x.end < root.interval.start ) { root.left = remove(x, root.left); } else if ( root.left != null && root.right != null) { root.interval = findMin(root.right).interval; root.right = remove( root.interval, root.right); } else { root = ( root.left != null ) ? root.left : root.right; } return root; } BSTNode findKey(int val, BSTNode root) { if (root == null) return null; if (root.interval.start > val) { return findKey(val, root.left); } else if (root.interval.end < val) { return findKey(val, root.right); } else return root; } BSTNode addKey(int val, BSTNode root) { if (root == null) { root = new BSTNode( new Interval(val, val) ); } else if (root.interval.start > val) { root.left = addKey(val, root.left); } else if (root.interval.end < val) { root.right = addKey(val, root.right); } return root; } void inOrder(BSTNode root) { if (root != null) { inOrder(root.left); list.add(root.interval); inOrder(root.right); } } /** Initialize your data structure here. */ BSTNode root; List list = new ArrayList(); public SummaryRanges() { root = null; } public void addNum(int val) { if (root == null) { root = addKey(val, root); } else { if ( findKey(val, root) != null) return; BSTNode left = findKey(val-1, root); BSTNode right = findKey(val+1, root); if (left == null && right == null) { root = addKey(val, root); } else if (left != null && right == null) { left.interval.end++; } else if (left == null && right != null) { right.interval.start--; } else { Interval l = left.interval; int e = right.interval.end; root = remove(right.interval, root); l.end = e; } } } public List getIntervals() { list.clear(); inOrder(root); return list; }} 转载地址：http://cbqvb.baihongyu.com/