K-way merge of sorted lists
Java
Hard
5 views
Problem Description
Task: merge k sorted int arrays into one sorted array using a priority queue.
Output Format
Return value
Constraints
Total elements can be large; do not re-sort everything.
Official Solution
static int[] kWayMerge(int[][] lists){java.util.PriorityQueue<int[]> pq=new java.util.PriorityQueue<>((a,b)->Integer.compare(a[0],b[0]));int total=0;for(int i=0;i<lists.length;i++){total+=lists[i].length;if(lists[i].length>0) pq.add(new int[]{lists[i][0],i,0});}int[] res=new int[total];int idx=0;while(!pq.isEmpty()){int[] cur=pq.poll();res[idx++]=cur[0];int li=cur[1],pi=cur[2]+1; if(pi<lists[li].length) pq.add(new int[]{lists[li][pi],li,pi});}return res;}
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!