Merge Sorted Array

2/23/2018 update
从大到小merge， 可以不用考虑nums1里面数的位置问题。如果nums1[i]很大就被一道后面去了，如果nums[i]很小，就保持不变就行了。nums1[i]不可能移到前面。最后只需要检查nums2是否为空。
Solution:

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1;
        int j = n - 1;
        int t = m + n - 1;
        while (i >= 0 && j >= 0) {
            if(nums1[i] < nums2[j]) {
                nums1[t--] = nums2[j--];
            } else {
                nums1[t--] = nums1[i--];
            }
        }

        while (j >= 0) {
            nums1[t--] = nums2[j--];
        }
    }
}

--------------------------------------------------------------------------------------------------------------------------

思路：
从大到小开始merge, 如果从小到大，需要把A后面的数往后挪，挪数组的时间复杂度是O(n)。

代码如下

 public class Solution {  
   /*  
    * @param A: sorted integer array A which has m elements, but size of A is m+n  
    * @param m: An integer  
    * @param B: sorted integer array B which has n elements  
    * @param n: An integer  
    * @return: nothing  
    */  
   public void mergeSortedArray(int[] A, int m, int[] B, int n) {  
     // write your code here  
     int i = m-1;  
     int j = n-1;  
     int q = m + n -1;  
     while(i >= 0 && j >= 0) {  
       if(A[i] > B[j]) {  
         A[q--] = A[i--];  
       } else {  
         A[q--] = B[j--];  
       }  
     }  
     while(i >= 0) {  
       A[q--] = A[i--];  
     }  
     while(j >= 0) {  
       A[q--] = B[j--];  
     }  
   }  
 }