總結:
- 要排序two dimensional array需要先寫一個comparator, 然後用 Array.sort(nums, comparator);
參考: https://stackoverflow.com/questions/15452429/java-arrays-sort-2d-array
另一篇重寫comparator跟據學生學號排序學生object的文章: https://blog.csdn.net/yongh701/article/details/44131051
2.別人代碼總結:
- 用List<int []> 儲存two dimensional array int [][]
e.g. List<int []> res = new ArrayList<>(); - intervals[0] 代表 intervals[][] 的第一組 e.g. [[1,2],[3,4]]
intervals[0]代表[1,2], intervals[1]代表[3,4]
學習重寫comparator之前首先要知道comparator類如何運作:
例子:
public static void main(String[] args) throws IOException {
final Double[][] doubles = new Double[][]{{5.0, 4.0}, {1.0, 1.0}, {4.0, 6.0}};
final Comparator<Double[]> arrayComparator = new Comparator<Double[]>() {
@Override
public int compare(Double[] o1, Double[] o2) {
return o1[0].compareTo(o2[0]);
}
};
Arrays.sort(doubles, arrayComparator);
for (final Double[] arr : doubles) {
System.out.println(Arrays.toString(arr));
}
}
comparator模版:
Comparator<想要compare的類> arrayComparator = new Comparator<想要compare的類>(){
@Override
public int compare(想要compare的類 想要compare的名1, 想要compare的類 想要compare的類2){
//可以直接使用a.compareTo(b) 來獲取1/-1/0 或者 使用其他方法如參考連結例子中使用了s1.s_ no>s2.s_no return 1 , else if (s1.s_no<s2.s_no return -1), else 0; 重寫comparator 類
return 1/-1/0; //return 1代表"想要compare的名1">"想要compare的名2", -1代表小於, 0代表相等
思路:
先跟據intervals中的start time 排序, 創建res list
先放第一組intervals進res list
再將res list中的最後一組數組 與 intervals 組中第一數組 (now) 比較 e.g. [1,3] 比較 [2,6]
如current的end 大過 now 的end (3>2), 將current 的end 改變now 的end 否則 如3<2, 將now加入result list
繼續將current與 intervals數組中的下一個數組 比較 e.g. [1,6] 比較 [8,10], 因為6小於8, 將[8,10]加入result list
我第一次寫的錯誤代碼:
class Solution {
public int[][] merge(int[][] intervals) {
//corner case
if (intervals.length==0)
//sort arrays 跟據start數值
Arrays.sort(intervals, new Comparator <int []> (){
@Override
//重寫compare 方法
public int compare (int [] o1, int [] o2){
return Integer.compare(o1[0],o2[0]);
}
});
//創建res list
List<List<Integer>> res = new ArrayList<>();
//先放第一組intervals進res list
if (intervals.length==0) return res;
res.add(new List<Integer>(){intervals[0][0],intervals[0][1]});
if (intervals.length==1) return res;
for (int i=1; i<intervals.length; i++){
//current is res list的最後一個list
List<Integer> current = res.get(res.size()-1);
//if curernt的end 大於或等於 now的start --> overlap
if (current.get(1)>=intervals[i][0]){
如current的end小於now 的end, 將current的end改為now的end
if (current.get(1)>intervals[i][1]){
//記錄current的start
int start = current.get(0);
res.remove(res.szie()-1);
res.add(new List<Integer>(){start,intervals[i][1]});
}
//否則 如current的end大於now 的end, 不需加入now (now is在比較的interval list)
}
//current的end 小於now的start, 把now加入res list
else {
res.add(new List<Integer>(){intervals[i][0],intervals[i][1]});
}
}
return res;
}
}
修改後的ac代碼:
class Solution {
public int[][] merge(int[][] intervals) {
//sort arrays 跟據start數值
Arrays.sort(intervals, new Comparator <int []> (){
@Override
//重寫compare 方法
public int compare (int [] o1, int [] o2){
return Integer.compare(o1[0],o2[0]);
}
});
//創建res list
List<int []> res = new ArrayList<>();
//先放第一組intervals進res list
//corner case
if (intervals.length==0) return res.toArray(new int[res.size()][]);
res.add(intervals[0]);
for (int i=1; i<intervals.length; i++){
//current is res list的最後一個list
int[] current = res.get(res.size()-1);
//if curernt的end 大於或等於 now的start --> overlap
if (current[1]>=intervals[i][0]){
//如current的end小於now 的end, 將current的end改為now的end
if (current[1]<=intervals[i][1]){
//記錄current的start
int start = current[0];
res.remove(res.size()-1);
res.add(new int []{start,intervals[i][1]});
}
//否則 如current的end大於now 的end, 不需加入now (now is在比較的interval list)
}
//current的end 小於now的start, 把now加入res list
else {
res.add(new int []{intervals[i][0],intervals[i][1]});
}
}
return res.toArray(new int[res.size()][]);
}
}
別人ac代碼:
class Solution {
public int[][] merge(int[][] intervals) {
if(intervals.length <= 1)
return intervals;
Arrays.sort(intervals, (i1, i2) -> Integer.compare(i1[0], i2[0]));
List<int[]> result = new ArrayList<>();
int[] newInterval = intervals[0];
result.add(newInterval);
for(int[] interval : intervals){
if(newInterval[1] >= interval[0])
newInterval[1] = Math.max(newInterval[1], interval[1]);
else{
newInterval = interval;
result.add(newInterval);
}
}
return result.toArray(new int[result.size()][]);
}
}
