版权声明:本文为博主原创文章,未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434787
详细代码可以fork下Github上leetcode项目,不定期更新。
题目摘自leetcode:
思路:
该开始使用了for循环中加入了stack的结构,但发现这种思路很难逼近答案。正确的思路应该为:
for {
if (合并) 合并操作
else 记录答案
}
代码如下:
public List<Interval> merge(List<Interval> intervals) {
if (intervals.size() == 0) return new ArrayList<>();
Collections.sort(intervals, (a,b) -> a.start != b.start ? a.start - b.start : a.end - b.end);
List<Interval> ans = new ArrayList<>();
int start = intervals.get(0).start;
int end = intervals.get(0).end;
for (Interval inter : intervals){
if (end > inter.start){
end = Math.max(end, inter.end);
}else{
ans.add(new Interval(start, end));
start = inter.start;
end = inter.end;
}
}
//合并到一半的区间最后需要统一加上
ans.add(new Interval(start,end));
return ans;
}
思路:
可以跟着上一题的思路来,类似于插入排序,找到适当的位置,把newIntervals插入到指定位置,在它之前的所有区间可以直接add,与它相交的需要更新Interval。代码如下:
public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
if (intervals.size() == 0) return Collections.singletonList(newInterval);
List<Interval> ans = new ArrayList<>();
int i = 0;
while (i < intervals.size() && newInterval.start > intervals.get(i).start) i++;
int target = i - 1 == -1 ? 0 : i - 1;
for (int j = 0; j < target; j++){
ans.add(intervals.get(j));
}
intervals.add(i, newInterval);
int start = intervals.get(target).start;
int end = intervals.get(target).end;
for (int j = target; j < intervals.size(); j++){
if (end >= intervals.get(j).start){
end = Math.max(end, intervals.get(j).end);
}else{
ans.add(new Interval(start,end));
start = intervals.get(j).start;
end = intervals.get(j).end;
}
}
ans.add(new Interval(start,end));
}
还有一种更聪明的做法,在筛选区间时有一定的技巧。
a. intervals[i].end < newInterval.start 可以直接排除
b. intervals[i].start > newInterval.end 可以直接排除
中间区间的更新都是与newInterval有交集,所以更新:
交集中的最小start和交集中的最大end即可
代码如下:
public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
if (intervals.size() == 0) return Collections.singletonList(newInterval);
List<Interval> ans = new ArrayList<>();
int i = 0;
while (i < intervals.size() && newInterval.start > intervals.get(i).end) ans.add(intervals.get(i++));
while (i < intervals.size() && intervals.get(i).start <= newInterval.end){
newInterval = new Interval(
Math.min(newInterval.start, intervals.get(i).start),
Math.max(newInterval.end, intervals.get(i).end));
i++;
}
ans.add(newInterval);
while (i < intervals.size()) ans.add(intervals.get(i++));
return ans;
}
一种朴素的做法,时间复杂度为O(nlogn)O(n\log n),可以参考summary Range的思路。
思路:
不管三七二十一,把数据全部添加到set集合中来(没有维护大小关系),惰性做法,当要返回区间时,开始计算,对nums进行排序,连续的值可以合并成一个区间。
代码如下:
public class SummaryRanges {
Set<Integer> nums;
public SummaryRanges(){
nums = new HashSet<>();
}
public void addNum(int val){
nums.add(val);
}
public List<Interval> getIntervals(){
Integer[] num = nums.toArray(new Integer[0]);
Arrays.sort(num);
int[] dp = new int[num.length];
for (int i = 1; i < num.length; i++){
if (num[i] - num[i-1] == 1) dp[i] = dp[i-1] + 1;
}
List<Interval> ans = new ArrayList<>();
for (int i = 0; i < num.length; i++){
int same = num[i];
while (i < num.length && num[i] - dp[i] == same) i++;
if (same == num[i-1]) ans.add(new Interval(same,same));
else ans.add(new Interval(same, num[i-1]));
i--;
}
return ans;
}
}
这种做法相当糟糕,在加入val时,并没有维护它的顺序,导致每当getIntervals为了更好的合并都需要排序一次,这题还可以参考第二题的思路,每当加入一个元素时,不断维护该list。时间复杂度可以降到O(n)O(n)。
代码如下:
public class SummaryRanges {
List<Interval> ans = new ArrayList<>();
public SummaryRanges(){
ans = new ArrayList<>();
}
public void addNum(int val){
Interval newInterval = new Interval(val, val);
List<Interval> tmp = new ArrayList<>();
if (ans.size() == 0){
tmp.add(newInterval);
ans = tmp;
return;
}
int i = 0;
while (i < ans.size() && newInterval.start > ans.get(i).end + 1) tmp.add(ans.get(i++));
while (i < ans.size() && newInterval.end + 1 >= ans.get(i).start){
newInterval = new Interval(
Math.min(ans.get(i).start, newInterval.start),
Math.max(ans.get(i).end, newInterval.end));
i++;
}
tmp.add(newInterval);
while (i < ans.size()) tmp.add(ans.get(i++));
ans = tmp;
}
public List<Interval> getIntervals(){
return ans;
}
public static void main(String[] args) {
SummaryRanges sr = new SummaryRanges();
sr.addNum(1);
sr.addNum(3);
sr.addNum(2);
}
}
上述代码的复杂度为O(n)O(n),主要原因在于查找操作中,需要遍历ans List,找到合适的两个断点,才进行区间更新。
换句话说,我们完全可以在一个有序的List中进行二分查找,只需要找到符合:
a. ans.get(i).end + 1 >= newInterval.start
b. ans.get(i).start <= newInterval.end + 1
条件a的查找很简单,二分查找有序list中的end,就能找到待插入的位置i
条件b的查找可以转换成:
ans.get(i).start > newInterval.end + 1
因此,也可以二分查找有序list中的start,能找到终止位置i
但上述代码使用了ArrayList,实施二分查找较复杂,但至少给了我们一个O(log n)的思路。
支持二分查找,且同时支持O(log n)的插入的数据结构还有Tree,所以我们可以实现一个BST,来做查找和插入的操作。
如何表达val 和 区间的关系?
TreeMap<val, interval>这种数据结构能够完美表达。
构建思路:
就一条,遇到合并的情况,把区间start高的,合并到start低的区间上。
如:
[1,1],[2,2] -> [1,2] (删除第二个区间,修改第一个区间的end)
代码如下:
TreeMap<Integer, Interval> 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 && val == h - 1){
tree.get(l).end = tree.get(h).end;
tree.remove(h);
}
else if (h != null && val == h - 1){
tree.put(val, new Interval(val,tree.get(h).end));
tree.remove(h);
}
else if (l != null && tree.get(l).end + 1 >= val){
tree.get(l).end = Math.max(val, tree.get(l).end);
}
else {
tree.put(val, new Interval(val,val));
}
}
查找,删除,插入的时间复杂度均为O(logn)O(\log n),完美的结构。