Saturday, February 7, 2015

Merge k sorted arrays

Merge 'k' sorted arrays, each array may have max 'n' elements 
This question follows the same approach as Merge k sorted lists.  The only difference is that now we are dealing with array, we lose the advantage of the "next" pointer. I use a structure that record the array's position at the input list, the index of the element in the array and the element itself to solve the problem.


/**
 * Merge 'k' sorted arrays, each array may have max 'n' elements
 * @author shirleyyoung
 *
 */
import java.util.*;
public class MergeKSortedArrays {
 private static class Position {
  //the position of the array in the list
  int listPos;
  //the index of current element
  int index;
  //the element
  int element;
  public Position(int listPos, int index, int element) {
   this.listPos = listPos;
   this.index = index;
   this.element = element;
  }
 }
 public static List mergeArrays(List arrays) {
  if (arrays == null || arrays.size() == 0) {
   throw new IllegalArgumentException("Invalid input!");
  }
  PriorityQueue pq = new PriorityQueue (new Comparator() {
   public int compare(Position a, Position b) {
    if (a.element - b.element < 0) 
     return -1;
    else if (a.element - b.element > 0)
     return 1;
    else if (a.listPos - b.listPos < 0)
     return -1;
    else if (a.listPos - b.listPos > 0)
     return 1;
    else if (a.index - b.index < 0)
     return -1;
    else if (a.index - b.index > 0)
     return 1;
    else
     return 0;
   }
  });
  
  for (int i = 0; i < arrays.size(); i++) {
   pq.add(new Position(i, 0, arrays.get(i)[0]));
  }
  List rst = new ArrayList ();
  while (!pq.isEmpty()) {
   Position curr = pq.poll();
   rst.add(curr.element); 
   if (curr.index < arrays.get(curr.listPos).length - 1) {
    int nextIndex = curr.index + 1;
    int next = arrays.get(curr.listPos)[nextIndex];
    pq.add(new Position(curr.listPos, nextIndex, next)); 
   }
  }
  return rst;
 }

 public static void main(String[] args) {
  List arrays = new ArrayList ();
  int[] a = {1, 3, 5, 7, 10};
  int[] b = {2, 4, 6, 8};
  int[] c = {9, 12, 15};
  int[] d = {11, 13, 14, 16, 17};
  int[] e = {11, 12, 13, 14, 15};
  arrays.add(a);
  arrays.add(b);
  arrays.add(c);
  arrays.add(d);
  arrays.add(e);
  
  //System.out.println(arrays.size());
  List rst = mergeArrays(arrays);
  for (Integer i : rst) {
   System.out.print(i + " ");
  }
  System.out.println();
 }
}

2 comments:

  1. Thanks for code and explanation. I have a problem in running your code. When I copy-paste your code, I get error in lines 45 and 53; so, I cannot run it! could you please help me, what I should do? Thanks

    ReplyDelete
    Replies
    1. I don't know why it doesn't work for you. However, you can check my git (https://github.com/shirleyyoung0812/Facebook/blob/master/src/facebookCoding/MergeKSortedArrays.java). I just ran it, it should work.

      Moreover, I realize this is not a good solution, so I wrote another solution. See this post. http://shirleyisnotageek.blogspot.com/2015/08/merge-k-sorted-linked-listsarrays.html

      Delete