Merge K sorted arrays

1389 ワード

Input: N sorted arrays of integers (in ascending order)
Output: Final sorted array of integers
 
public static class Node {
    int index = 0;
    List<Integer> list;
    public Node(List<Integer> list) {
        this.list = list;
    }
    
    public int peek() {
        return list.get(index);
    }

    public int next() {
        return list.get(index++);
    }
    
    public boolean hasNext() {
        return index < list.size();
    }
}
List<Integer> sortData(List<List<Integer>> numArray) {
    List<Integer> result = new ArrayList<>();
    Queue<Node> queue = new PriorityQueue<>(new Comparator<Node>(){
        public int compare(Node n1, Node n2) {
            return n1.peek() - n2.peek();
        }
    });
    for(List<Integer> list:numArray) {
        if(list != null && list.size() > 0) {
            queue.offer(new Node(list));
        }
    }
    while(!queue.isEmpty()) {
        Node node = queue.poll();
        result.add(node.next());
        if(node.hasNext()) {
            queue.offer(node); 
        }
    }
    return result;
}