34 Merge Sorted Arrays II

kamia

Mergesort

1.     public static int[] mergeSortedArrays(int [][] a) {
   
2.         if(a.length == 0 || a[0].length == 0)   return new int[]{};
   
3.         return helper(a, 0, a.length-1);
   
4.     }
   
5. 
   
6.     private static int[] helper(int[][] a, int i, int j) {
   
7.         if(i == j)  return a【i】;
   
8.         int mid = i + (j-i)/2;
   
9.         int[] l1 = helper(a, i, mid);
   
10.         int[] l2 = helper(a, mid+1, j);
    
11.         return merge(l1, l2);
    
12.     }
    
13. 
    
14.     private static int[] merge(int[] a, int[] b) {
    
15.         int[] c = new int[a.length+b.length];
    
16.         int i = 0, j = 0, k = 0;
    
17.         while(i < a.length && j < b.length) {
    
18.             if(a【i】 <= b[j]) {
    
19.                 c[k++] = a[i++];
    
20.             } else {
    
21.                 c[k++] = b[j++];
    
22.             }
    
23.         }
    
24.         while(i < a.length) {
    
25.             c[k++] = a[i++];
    
26.         }
    
27.         while(j < b.length) {
    
28.             c[k++] = b[j++];
    
29.         }
    
30.         return c;
    
31.     }

复制代码

Sophia

Great post~~~

landscape1250

helpful