合并排序好的数组

问题

给定两个排序好的数组A和B,把B合并到A并保持排序。

public class Solution {
    public void merge(int A[], int m, int B[], int n) {
//write your code here

}
}

注意:
假定A有足够的额外的容量储存B的内容,m和n分别为A和B的初始化元素的个数。要求算法复杂度在O(m+n)。

分析:
为了避免使用额外的空间,这里的技巧就是从后向前合并。代码很简单,但是也要求基本功扎实。

public class Solution {
public void merge(int A[], int m, int B[], int n) {
int e = m+n;
while(m>0 && n>0){
if(A[m-1]>B[n-1]){
A[–e]=A[–m];
}
else{
A[–e]=B[–n];
}
}
if(n>0){
System.arraycopy(B,0,A,0,n);
}
}
}

标签