Merge K sorted arrays
1389 ワード
Input: N sorted arrays of integers (in ascending order)
Output: Final sorted array of integers
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;
}