Given _k _sorted integer arrays, merge them into one sorted array.
Example
Given 3 sorted arrays:
[
[1, 3, 5, 7],
[2, 4, 6],
[0, 8, 9, 10, 11]
]
return[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11].
Do it in O(N log k).
_N _is the total number of integers.
_k _is the number of arrays.
2.Code
本题目需要一个helper class来确定他们的位置和值，跟merge k sorted list思路基本一致。也是用最小堆来实现
注意用来判断是不是这一行最后一个element的写法
class Points{
int x;
int y;
int value;
public Points(int x,int y,int value){
this.x=x;
this.y=y;
this.value=value;
}
}
public class Solution_486 {
/**
* @param arrays k sorted integer arrays
* @return a sorted array
*/
public List<Integer> mergekSortedArrays(int[][] arrays) {
List<Integer> result=new ArrayList<Integer>();
Queue<Points> queue=new PriorityQueue<Points>(arrays.length,new Comparator<Points>(){
public int compare(Points a,Points b){
return a.value-b.value;
}
});
//put the first element of each line in queue
for(int i=0;i<arrays.length;i++){
if(arrays[i].length>0){
Points current=new Points(i,0,arrays[i][0]);
queue.offer(current);
}
}
while(!queue.isEmpty()){
Points min=queue.poll();
result.add(min.value);
//用来判断是不是这一行的终点
if(min.y+1<arrays[min.x].length){
Points next=new Points(min.x,min.y+1,arrays[min.x][min.y+1]);
queue.offer(next);
}
}
return result;
}
}