64. Merge Sorted Array

image.png

hhh 竟然这样也可以过，简直是。。。

class Solution {
public:
    /*
     * @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
     */
    void mergeSortedArray(int A[], int m, int B[], int n) {
        // write your code here
        int j = 0;
        for(int i = m ; i< m+n; i++){
            A[i] = B[j];
            j++;
        }
        sort(A,A+m+n);
    }
};

解法二：
从后往前填补数字，把从小到大的排序问题转换为从大到小的排序。

class Solution {
public:
    /*
     * @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
     */
    void mergeSortedArray(int A[], int m, int B[], int n) {
        // write your code here
        int l = m + n - 1;
        m--;
        n--;
        while(m >= 0 && n >= 0){
            if(A[m] > B[n]){
                A[l--] = A[m];
                m--;
            }
            else{
                A[l--] = B[n];
                n--;
            }
        }
        if(n >= 0){
            while(n >= 0){
                A[l--] = B[n--];
            }
        }
        else{
            while(m >= 0){
                A[l--] = A[m--];
            }
        }
        
    }
};