Two sorted 2D arrrays, get the third one sortedUpdate 2015 - 03 - 31:
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
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 ListsortArray (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