My code:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.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 Solution {
public List<Interval> merge(List<Interval> intervals) {
ArrayList<Interval> result = new ArrayList<Interval>();
if (intervals == null || intervals.size() == 0)
return result;
if (intervals.size() == 1) {
result.add(intervals.get(0));
return result;
}
int[] begin = new int[intervals.size()];
HashMap<Integer, Integer> range = new HashMap<Integer, Integer>();
range.put(intervals.get(0).start, intervals.get(0).end);
begin[0] = intervals.get(0).start;
for (int i = 1; i < intervals.size(); i++) {
begin[i] = intervals.get(i).start;
if (range.containsKey(intervals.get(i).start) && intervals.get(i).end <= range.get(begin[i]))
continue;
else
range.put(intervals.get(i).start, intervals.get(i).end);
}
Arrays.sort(begin);
Interval interval = new Interval(begin[0], range.get(begin[0]));
for (int i = 1; i <= begin.length; i++) {
if (i == begin.length)
result.add(interval);
else if (begin[i] > interval.end) {
result.add(interval);
interval = new Interval(begin[i], range.get(begin[i]));
}
else if (begin[i] < interval.start) {
if (range.get(begin[i]) <= range.get(begin[i - 1]))
interval = new Interval(begin[i], range.get(begin[i - 1]));
else
interval = new Interval(begin[i], range.get(begin[i]));
}
else if (range.get(begin[i]) > interval.end)
interval = new Interval(interval.start, range.get(begin[i]));
else
continue;
}
return result;
}
public static void main(String[] args) {
Solution test = new Solution();
Interval a0 = new Interval(1, 4);
Interval a1 = new Interval(1, 4);
ArrayList<Interval> result = new ArrayList<Interval>();
result.add(a0);
result.add(a1);
System.out.println(test.merge(result));
}
}
My test result:
這道題目不算很難邓梅。一直在思考一個(gè)問題励背，如何保存這種范圍的映射漂洋，這種start和end的映射祖乳。最后還是決定用HashMap， key -> start, value -> end.
將所有的數(shù)據(jù)保存在哈希表中秉氧，
同時(shí)眷昆，將所有的開頭數(shù)字，保存在begin數(shù)組中汁咏。注意保存哈希表的時(shí)候亚斋，如果當(dāng)前頭在哈希表中已經(jīng)存在的話，需要判斷下其尾是否大于哈希表對應(yīng)的val攘滩。如果不是帅刊，則跳過，如果是漂问，則更新哈希表赖瞒。
然后對 begin[] 排序女揭。
然后按照一定的規(guī)則，處理這個(gè)數(shù)組栏饮，不斷地插入新的interval到結(jié)果中去吧兔。
差不多就這樣了。
**
總結(jié)： Array, sort, hash table
今天總算把三道題目的量完成了袍嬉。中午和初中同學(xué)吃飯境蔼。突然明白了那么一句話。
我努力了這么久伺通，就是為了和你喝一杯咖啡箍土。
感覺他們的世界，和我的不同罐监。他們對知識的掌握程度吴藻，也遠(yuǎn)高于我。但同樣的笑诅，他們也需要考慮汽車在哪里買便宜调缨。租的房子干不干凈。這些他們也不能幸免吆你。
然后弦叶，我要潛下心來，默默地妇多，變強(qiáng)伤哺。
最后，希望選課順利者祖！
**
Anyway, Good luck, Richardo!
My code:
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.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 Solution {
public List<Interval> merge(List<Interval> intervals) {
if (intervals == null || intervals.size() == 0)
return intervals;
Collections.sort(intervals, new Comparator<Interval>() {
public int compare(Interval o1, Interval o2) {
// int start1 = o1.start;
// int start2 = o2.start;
// int end1 = o1.end;
// int end2 = o2.end;
// if (start1 == start2 && end1 == end2)
// return 0;
// else if (start1 <= start2 && end1 <= end2)
// return -1;
// else
// return 1;
return o1.start - o2.start;
}
});
for (int i = 1; i < intervals.size(); i++) {
int frontStart = intervals.get(i - 1).start;
int frontEnd = intervals.get(i - 1).end;
int backStart = intervals.get(i).start;
int backEnd = intervals.get(i).end;
if (backStart > frontEnd)
continue;
else {
intervals.get(i - 1).start = Math.min(frontStart, backStart);
intervals.get(i - 1).end = Math.max(frontEnd, backEnd);
intervals.remove(i);
i--;
}
}
return intervals;
}
public static void main(String[] args) {
Interval a1 = new Interval(1, 3);
Interval a2 = new Interval(2, 5);
Interval a3 = new Interval(6, 7);
Interval a4 = new Interval(3, 4);
ArrayList<Interval> intervals = new ArrayList<Interval>();
intervals.add(a1);
intervals.add(a2);
intervals.add(a3);
intervals.add(a4);
Solution test = new Solution();
System.out.println(test.merge(intervals));
}
}
這是我自己寫的立莉，直接在里面改元素。
但是速度較慢七问。
為什么呢蜓耻？
因?yàn)槲矣幸粋€(gè)刪除操作。鏈表的刪除操作復(fù)雜度是O(n),所以如果測試案例的重合元素很多械巡，我的速度會很慢很慢刹淌。
于是有了一個(gè)改進(jìn)方法，就是新建一個(gè)ArrayList<...> ret,
然后把需要塞進(jìn)去的讥耗，已經(jīng)更新好了的interval放進(jìn)去有勾，這樣就不會再有刪除操作了。同樣也是遍歷整個(gè)鏈表古程。鏈表的.add()并不是很消耗時(shí)間的操作蔼卡。我就懶得寫了，但是速度應(yīng)該會更快挣磨。
然后就出現(xiàn)了一個(gè)問題雇逞，以前從來沒有碰到過：
Line 19: java.lang.IllegalArgumentException: Comparison method violates its general contract!
我查了下荤懂，大概是，
如果 A = B, 那么 B = A, 而我的comparator方法寫得可能違背了這一點(diǎn)喝峦。
Collections.sort(intervals, new Comparator() {
public int compare(Object o1, Object o2) {
int start1 = ((Interval) o1).start;
int start2 = ((Interval) o2).start;
if (start1 <= start2)
return -1;
else
return 1;
}
});
這是那段錯(cuò)誤的代碼势誊。我改了下，
Collections.sort(intervals, new Comparator<Interval>() {
public int compare(Interval o1, Interval o2) {
// int start1 = o1.start;
// int start2 = o2.start;
// int end1 = o1.end;
// int end2 = o2.end;
// if (start1 == start2 && end1 == end2)
// return 0;
// else if (start1 <= start2 && end1 <= end2)
// return -1;
// else
// return 1;
return o1.start - o2.start;
}
});
如果直接用注釋的部分谣蠢，是對的粟耻。用當(dāng)前部分也是對的。
我還是不能很好地理解這個(gè)錯(cuò)誤眉踱。等回了學(xué)校再仔細(xì)研究下挤忙。
然后我看了以前的做法，竟然可以用HashMap來做谈喳，也果真是巧妙册烈！
我又自己重寫了下，錯(cuò)了好幾次才AC婿禽。思路和代碼比之前要簡潔很多赏僧。
但其實(shí)和我上面的版本差不多的。就是一個(gè)排序扭倾。一個(gè)用Comparator實(shí)現(xiàn)淀零，一個(gè)用HashMap實(shí)現(xiàn)。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.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 Solution {
public List<Interval> merge(List<Interval> intervals) {
ArrayList<Interval> result = new ArrayList<Interval>();
if (intervals == null || intervals.size() == 0)
return result;
int[] begin = new int[intervals.size()];
HashMap<Integer, Integer> range = new HashMap<Integer, Integer>();
for (int i = 0; i < intervals.size(); i++) {
int start = intervals.get(i).start;
int end = intervals.get(i).end;
begin[i] = start;
if (range.containsKey(start) && range.get(start) >= end)
continue;
else
range.put(start, end);
}
Arrays.sort(begin);
result.add(new Interval(begin[0], range.get(begin[0])));
for (int i = 1; i < begin.length; i++) {
if (begin[i] == begin[i - 1])
continue;
else {
if (begin[i] > result.get(result.size() - 1).end)
result.add(new Interval(begin[i], range.get(begin[i])));
else
result.get(result.size() - 1).end = Math.max(result.get(result.size() - 1).end, range.get(begin[i]));
}
}
return result;
}
public static void main(String[] args) {
Solution test = new Solution();
Interval a0 = new Interval(2, 3);
Interval a1 = new Interval(4, 5);
Interval a2 = new Interval(6, 7);
Interval a3 = new Interval(8, 9);
Interval a4 = new Interval(1, 10);
ArrayList<Interval> result = new ArrayList<Interval>();
result.add(a0);
result.add(a1);
result.add(a2);
result.add(a3);
result.add(a4);
System.out.println(test.merge(result));
}
}
**
記住了膛壹，鏈表的remove操作很費(fèi)時(shí)間驾中，決定性浪費(fèi)時(shí)間！
能不用就不用把模聋！
還有一個(gè)comparator 問題沒有搞清楚肩民！
**
Anyway, Good luck, Richardo!
More efficient solution:
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 Solution {
public List<Interval> merge(List<Interval> intervals) {
ArrayList<Interval> ret = new ArrayList<Interval>();
if (intervals == null || intervals.size() == 0)
return ret;
Collections.sort(intervals, new Comparator<Interval>() {
public int compare(Interval o1, Interval o2) {
return o1.start - o2.start;
}
});
Interval preInterval = intervals.get(0);
for (int i = 1; i < intervals.size(); i++) {
Interval curr = intervals.get(i);
if (curr.start > preInterval.end) {
ret.add(preInterval);
preInterval = curr;
}
else {
Interval merge = new Interval(preInterval.start, Math.max(preInterval.end, curr.end));
preInterval = merge;
}
}
ret.add(preInterval);
return ret;
}
}
Anyway, Good luck, Richardo!
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 Solution {
public List<Interval> merge(List<Interval> intervals) {
List<Interval> ret = new ArrayList<Interval>();
if (intervals == null || intervals.size() == 0) {
return ret;
}
ret.add(intervals.get(0));
for (int i = 1; i < intervals.size(); i++) {
Interval curr = intervals.get(i);
int j = ret.size() - 1;
for (; j >= 0; j--) {
Interval cmp = ret.get(j);
if (cmp.end < curr.start) {
ret.add(j + 1, curr);
break;
}
else if (cmp.start <= curr.start) {
cmp.end = Math.max(cmp.end, curr.end);
break;
}
else if (cmp.start <= curr.end) {
cmp.start = curr.start;
cmp.end = Math.max(cmp.end, curr.end);
curr = cmp;
ret.remove(j);
}
else {
continue;
}
}
if (j < 0) {
ret.add(0, curr);
}
}
return ret;
}
}
自己寫了出來。應(yīng)該是 Insert sort 的一種變形链方。
注意地方是持痰，如果在向左遍歷途中，更新了一個(gè)Interval導(dǎo)致他的start變小了祟蚀，那么很有可能這個(gè)interval會覆蓋他前面一個(gè)interval共啃。這個(gè)時(shí)候就要把當(dāng)前Interval從鏈表里面刪除掉。然后更新curr指針暂题。讓他和下一個(gè)interval再次進(jìn)行比較。
list remove 操作究珊。一般情況下薪者，時(shí)間復(fù)雜度是O(n)
如果刪的是頭部或者尾部，時(shí)間復(fù)雜度是O(1)
以前的那個(gè)用HashMap實(shí)現(xiàn)sort的方法也是很有意思的剿涮。
Anyway, Good luck, Richardo! -- 09/02/2016
