Wednesday, March 11, 2015

Merge sorted array


Two sorted 2D arrrays, get the third one sorted
A = [["a", 1], ["b", 2]] sorted all elements have different names
B = [["a", 2], ["c", 3]] sorted
C = [["a", 3], ["b", 2], ["c", 3]] sorted
Update 2015 - 03 - 31: 
I realized that this problem can be solved in one pass.

public static struct[] sortArray2(struct[] A, struct[] B){
  if(A == null || A.length == 0 || B == null || B.length == 0)
   return null;
  int la = A.length, lb = B.length;
  struct[] rst = new struct[la + lb];
  int indexA = 0, indexB = 0, index = 0;
  while(indexA < la && indexB < lb){
   if(A[indexA].key.compareTo(B[indexB].key) <= 0)
    rst[index] = A[indexA++];
   else
    rst[index] = B[indexB++];
   if(index > 0 && rst[index].key.compareTo(rst[index - 1].key) == 0)
    rst[index - 1].val += rst[index].val;
   else
    index++;
  }
  while(indexA < la){
   rst[index] = A[indexA++];
   if(rst[index].key.compareTo(rst[index - 1].key) == 0)
    rst[index - 1].val += rst[index].val;
   else
    index++;
  }
  while(indexB < la){
   rst[index] = B[indexB++];
   if(rst[index].key.compareTo(rst[index - 1].key) == 0)
    rst[index - 1].val += rst[index].val;
   else
    index++;
  }
  while(index < rst.length)
   rst[index++] = null;
  return rst;
 }


 Merge two array first, then sum up all values with the same key. The only shortcoming of my code is that I use an extra list to store the intermediate merged list, which I haven't figured out a way to improve.


public class Sort2DArrays {
private static class struct{
  String key;
  int val;
  public struct(String k, int v){
   key = k;
   val = v;
  }
  public String toString(){
   return "[" + key + ", " + String.valueOf(val) + "]";
  }
 }
 public static List sortArray (struct[] A, struct[] B){
  if(A == null || A.length == 0 || B == null || B.length == 0)
   return null;
  List c = new ArrayList();
  int indexA = 0;
  int indexB = 0;
  while(indexA < A.length && indexB < B.length){
   if(A[indexA].key.compareTo(B[indexB].key) <= 0)
    c.add(A[indexA++]);
   else
    c.add(B[indexB++]);
  }
  while(indexA < A.length)
   c.add(A[indexA++]);
  while(indexB < B.length)
   c.add(B[indexB++]);
  List rst = new ArrayList();
  int index = 0;
  while(index < c.size()){
   int sum = 0;
   String k = c.get(index).key;
   while(index < c.size() && c.get(index).key.equals(k))
    sum += c.get(index++).val;
   rst.add(new struct(k, sum));
  }
  return rst;
 }
public static void main(String[] args) {
  struct[] A = new struct[4];
  A[0] = new struct("a", 1);
  A[1] = new struct("b", 2);
  A[2] = new struct("d", 4);
  A[3] = new struct("e", 5);
  struct[] B = new struct[4];
  B[0] = new struct("a", 2);
  B[1] = new struct("c", 3);
  B[2] = new struct("e", 4);
  B[3] = new struct("g", 6);
  for(struct i : sortArray(A, B)){
   System.out.println(i.toString());
  }
  System.out.println("");
  for(struct i : sortArray2(A, B)){
   if(i != null)
    System.out.println(i.toString());
  }
 }
}

No comments:

Post a Comment