题目截图
My initial solution: 可能产生 merge 的情况集中处理，可以减少代码量。查找处可以使用 Binary Search 优化。
class SummaryRanges {
ArrayList<Interval> list;
/** Initialize your data structure here. */
public SummaryRanges() {
list = new ArrayList<>();
}
public void addNum(int val) {
if (list.size() == 0) {
list.add(new Interval(val, val));
return;
}
int index = 0;
while (index < list.size() && list.get(index).start <= val) {
index++;
}
index--;
if (index < 0) {
Interval first = list.get(0);
if (first.start == val + 1) {
// case first interval = [4, 7], val = 3, update first interval to [3, 7]
first.start = val;
} else {
// case first interval = [4, 7], val = 2, add new interval [2, 2] in front of [4, 7]
list.add(0, new Interval(val, val));
}
} else if (index == list.size() - 1) {
Interval last = list.get(list.size() - 1);
if (last.end == val - 1) {
// case last interval = [3, 10], val = 11, update last interval to [3, 11]
last.end = val;
} else if (last.end < val - 1) {
// case last interval = [3, 10], val = 14, add new interva [14, 14] in the end
list.add(new Interval(val, val));
} else {
// case last interval = [3, 10], val = 5 included in the last interval
// do nothing
}
} else {
Interval curr = list.get(index);
Interval next = list.get(index + 1);
// here we have curr.start <= val && next.start > val
if (curr.end >= val) {
// case curr = [3, 5], next = [7, 10], val = 4 included in curr range
// do nothing
} else if (curr.end == val - 1){
if (next.start == curr.end + 2) {
// case curr = [3, 5], next = [7, 10], val = 6 connecting curr and next
curr.end = next.end;
list.remove(next);
} else {
// case curr = [3, 5], next = [8, 10], val = 6 new end for curr
curr.end = val;
}
} else if (next.start == val + 1) {
// case curr = [3, 5], next = [8, 10], val = 7 new start for next
next.start = val;
} else {
// case curr = [3, 5], next = [9, 10], val = 7 new interval to be added
list.add(index + 1, new Interval(val, val));
}
}
}
public List<Interval> getIntervals() {
return list;
}
}
题解使用了 TreeMap，StartTime => Interval. 之前面试的时候有想过使用 Binary Search Tree 来对 Interval 进行存储，但是没有想好 Data Structure 应该是什么样子的。
TreeMap 的一些性质：
TreeMap 使用 Red-Black Tree 来实现，key ordered
treeMap.lowerKey(target): returns biggest key lower than target
treeMap.higherKey(target): returns smallest key bigger than target
returns null for the two methods above if there is no such key.Example: TreeMap keys [1, 3, 6, 10], target 7 => lowerKey: 6, higherKey: 10
按 TreeMap 写的 initial Solution，有些逻辑是可以进行合并的。
class SummaryRanges {
TreeMap<Integer, Interval> map;
public SummaryRanges() {
map = new TreeMap();
}
public void addNum(int val) {
if (map.containsKey(val)) {
return;
}
Integer lower = map.lowerKey(val);
Integer higher = map.higherKey(val);
if (lower == null && higher == null) {
map.put(val, new Interval(val, val));
} else if (lower != null && higher != null) {
Interval lowerInterval = map.get(lower);
Interval higherInterval = map.get(higher);
if (lowerInterval.end >= val) {
// do nothing
} else if (lowerInterval.end + 1 == val) {
if (higherInterval.start == val + 1) {
lowerInterval.end = higherInterval.end;
map.remove(higher);
} else {
lowerInterval.end = val;
}
} else {
if (higherInterval.start == val + 1) {
higherInterval.start = val;
map.put(val, higherInterval);
map.remove(higher);
} else {
map.put(val, new Interval(val, val));
}
}
} else if (higher != null) {
Interval higherInterval = map.get(higher);
if (higherInterval.start == val + 1) {
higherInterval.start = val;
map.put(val, higherInterval);
map.remove(higher);
} else {
map.put(val, new Interval(val, val));
}
} else {
Interval lowerInterval = map.get(lower);
if (lowerInterval.end >= val) {
// do nothing
} else if (lowerInterval.end + 1 == val) {
lowerInterval.end = val;
} else {
map.put(val, new Interval(val, val));
}
}
}
public List<Interval> getIntervals() {
return new ArrayList<Interval>(map.values());
}
Simplified but need to debug:
public void addNum(int val) {
if (map.containsKey(val)) {
return;
}
Integer lower = map.lowerKey(val);
Integer higher = map.higherKey(val);
if (lower != null && higher != null) {
if (map.get(lower).end + 1 == val && map.get(higher).start == val + 1) {
map.get(lower).end = map.get(higher).end;
map.remove(higher);
} else if (map.get(lower).end + 1 == val) {
map.get(lower).end = val;
} else if (map.get(higher).start == val + 1) {
map.put(val, new Interval(val, map.get(higher).end));
map.remove(higher);
} else {
map.put(val, new Interval(val, val));
}
} else if (lower != null && higher == null && val <= map.get(lower).end + 1) {
map.get(lower).end = Math.max(val, map.get(lower).end);
} else if (lower == null && higher != null && map.get(higher).start == val + 1) {
map.put(val, new Interval(val, map.get(higher).end));
map.remove(higher);
} else {
map.put(val, new Interval(val, val));
}
}
网友评论