小明思考

Just a software engineer
posts - 124, comments - 36, trackbacks - 0, articles - 0
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

合并排序好的数组

Posted on 2013-04-18 13:44 小明 阅读(1275) 评论(0)  编辑  收藏 所属分类: 数据结构和算法
问题给定两个排序好的数组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);
        }
    }
}

只有注册用户登录后才能发表评论。
网站导航: