My code:
/**
* 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 {
TreeMap<Integer, Interval> map = new TreeMap<Integer, Interval>();
/** Initialize your data structure here. */
public SummaryRanges() {
}
public void addNum(int val) {
if (map.containsKey(val)) {
return;
}
Integer l = map.lowerKey(val);
Integer h = map.higherKey(val);
if (l != null && h != null && map.get(l).end + 1 == val && val + 1 == h) {
map.put(l, new Interval(l, map.get(h).end));
map.remove(h);
}
else if (l != null && map.get(l).end + 1 >= val) {
map.put(l, new Interval(l, Math.max(map.get(l).end, val)));
}
else if (h != null && val >= h - 1) {
map.put(val, new Interval(val, map.get(h).end));
map.remove(h);
}
else {
map.put(val,new Interval(val, val));
}
}
public List<Interval> getIntervals() {
return new ArrayList<Interval>(map.values());
}
}
/**
* Your SummaryRanges object will be instantiated and called as such:
* SummaryRanges obj = new SummaryRanges();
* obj.addNum(val);
* List<Interval> param_2 = obj.getIntervals();
*/
reference:
https://discuss.leetcode.com/topic/46887/java-solution-using-treemap-real-o-logn-per-adding
感覺這道題目沒什么意思。
主要就是熟悉下 TreeMap
他的特點就是 lowerKey(), higherKey()
Anyway, Good luck, Richardo! -- 09/29/2016
