Java合并两个升序数组

假如a,b是两个已排好序的升序数组,将数组b合并到a中,使a成为一个升序数组(这里假设a的长度大于等于a和b的元素个数之和)

3个回答

b的元素合并到a中,很可能涉及a中元素的移位,移位对于数组来说效率较低,所以建议把a和b的元素先合并到c中,然后再把c的地址赋给a;
那么a、b合并的代码如下:(假设a、b是int型的数组,如果是其他类型的数组要稍稍修改程序才能用,主要是修改数组类型定义和判断数组元素大小的地方)

    public int [] combine(int[] a, int[] b){
        if(a == null) return b;
        if(b == null) return a;

        int aIndex = 0;
        int bIndex = 0;
        int[] c = new int[a.length + b.length];
        int cIndex = 0;

        while(aIndex < a.length && bIndex < b.length){
            if(a[aIndex] <= b[bIndex]){
                c[cIndex++] = a[aIndex ++];
            }else{
                c[cIndex++] = b[bIndex ++];
            }
        }

        while(aIndex < a.length){
            c[cIndex++] = a[aIndex ++];
        }

        while(bIndex < b.length){
            c[cIndex++] = b[bIndex ++];
        }
        return c;
    }

import java.util.Arrays;

public class Test5 {

public static void main(String[] args) {
    int s[]={1,3,4,6,8,9,12};

    int b[]={0,2,5,7,10,11};
    int a[]=Arrays.copyOf(s, s.length+b.length);
    for(int i=s.length;i<a.length;i++){
        a[i]=b[i-s.length];
        System.out.print(a[i]+" ");
    }
    System.out.println();
    Arrays.sort(a);
    for(int i=0;i<a.length;i++)
        System.out.print(a[i]+" ");
}

}

wwwsssaaaddd
诸相非相 Arrays.sort采用并归排序,时间复杂度是O(n*log(n))。实际上可以优化到O(n)
4 年多之前 回复

手机码字不容易,设a的实际长度为n,b的实际长度为m,我们可以从a数组的地n+m-1位开始从后往前算哇,这样空间复杂就是常数了

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问