Given two sorted integer arrays A and B, merge B into A as one sorted array.

Note:

You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements from B. The number of elements initialized in A and B are m and nrespectively.

Solution1：新建ArrayList暂存merged list，后放回A

public class Solution {

    public void merge(int A[], int m, int B[], int n) {

        int length = m+n;

        ArrayList<Integer> merge = new ArrayList<Integer>();

        int posA =0, posB=0, i=0;

        while( i<length){

            if(posB>=n){merge.add(A[posA]); posA++; i++;}

            else if(posA>=m){ merge.add(B[posB]); posB++; i++;}

            else if(A[posA]<=B[posB]){merge.add(A[posA]); posA++; i++;}

            else{merge.add(B[posB]); posB++; i++;}

        }

        for(i=0; i<length;i++){

            A[i] = merge.get(i);

        }

    }

}

Solution2：可不能够不额外开辟空间？利用倒序。

public class Solution {

    public void merge(int A[], int m, int B[], int n) {

        int position = m+n-1;

        while(m>0 && n>0){

            if(A[m-1]>=B[n-1]) {

                A[position] = A[m-1];

                m--;

            }

            else{

                A[position] = B[n-1];

                n--; 

            }

            position--;

        }

        while(n>0){

            A[position] = B[n-1];

            n--;

            position--;

        }

    }

}

Solution1：再简单点？

public class Solution {

    public void merge(int A[], int m, int B[], int n) {

        for(int i=m+n-1; i>=0; i--) A[i]=((m>0)&&(n==0 || A[m-1]>=B[n-1]))?A[--m]:B[--n];

    }

}