Q:
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?
A:-----也可以用TreeMap
思路很直接: 就是用Set记录每个插入的。如果有重复的,就直接忽略
用List记录结果。
用Map记录 每个上下界 对应的interval,没加入一个新的数字,则 检查和修改map和list
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?
What if there are lots of merges and the number of disjoint intervals are small compared to the data stream's size?
用List记录结果。
用Map记录 每个上下界 对应的interval,没加入一个新的数字,则 检查和修改map和list
/** * 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<Interval> list ; Map<Integer, Interval> map; // record start and end only Set<Integer> set; // all found numbers /** Initialize your data structure here. */ public SummaryRanges() { list = new LinkedList<>(); map = new HashMap<>(); set = new HashSet<>(); } public void addNum(int val) { if(set.contains(val)) return; set.add(val); // check val+1 if(map.containsKey(val+1)){ Interval after = map.get(val+1); after.start = val; map.put(val, after); if(after.end != val+1) map.remove(val+1); if(map.containsKey(val-1)){ Interval before = map.get(val-1); list.remove(before); after.start = before.start; map.put(after.start, after); if(before.start != val -1 ) map.remove(val-1); } return; } // check val -1 if(map.containsKey(val-1)){ // cannot contains upper Interval before = map.get(val-1); before.end = val; if(before.start != val -1) map.remove(val-1); map.put(val,before); return; } // add a new interval, linearly Interval tmp = new Interval(val, val); for(int i = 0;i< list.size();i++){ if(list.get(i).start > val){ map.put(val,tmp); list.add(i,tmp); return; } } map.put(val, tmp); list.add(tmp); } public List<Interval> getIntervals() { return list; } } /** * Your SummaryRanges object will be instantiated and called as such: * SummaryRanges obj = new SummaryRanges(); * obj.addNum(val); * List<Interval> param_2 = obj.getIntervals(); */
No comments:
Post a Comment