486.Merge k Sorted Arrays

1.Description(Medium)

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].

Challenge

Do it in O(N log k).

• _N _is the total number of integers.

• _k _is the number of arrays.

Tags

Heap Priority Queue

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;
    }
}