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
     
       merge = new ArrayList
      
       ();        int posA =0, posB=0, i=0;        while( i
       
        =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
       
      
     

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];            }}