1. 首页
  2. 问题
  3. Java 如何将两个排序数组合并为一个排序数组？
一尘不染

Java 如何将两个排序数组合并为一个排序数组？

java

这是在采访中问我的，这是我提供的解决方案：

public static int[] merge(int[] a, int[] b) {

    int[] answer = new int[a.length + b.length];
    int i = 0, j = 0, k = 0;
    while (i < a.length && j < b.length)
    {
        if (a[i] < b[j])
        {
            answer[k] = a[i];
            i++;
        }
        else
        {
            answer[k] = b[j];
            j++;
        }
        k++;
    }

    while (i < a.length)
    {
        answer[k] = a[i];
        i++;
        k++;
    }

    while (j < b.length)
    {
        answer[k] = b[j];
        j++;
        k++;
    }

    return answer;
}

有没有更有效的方法可以做到这一点？

编辑：更正的长度方法。


阅读 757

收藏
2020-03-03

共2个答案

一尘不染

稍有改进，但是在主循环之后，System.arraycopy当到达另一个输入数组的末尾时，可以用来复制其中一个输入数组的结尾。但是，那不会改变O(n)你解决方案的性能特征。

2020-03-03
一尘不染 

public static int[] merge(int[] a, int[] b) {

    int[] answer = new int[a.length + b.length];
    int i = 0, j = 0, k = 0;

    while (i < a.length && j < b.length)  
       answer[k++] = a[i] < b[j] ? a[i++] :  b[j++];

    while (i < a.length)  
        answer[k++] = a[i++];


    while (j < b.length)    
        answer[k++] = b[j++];

    return answer;
}

稍微紧凑但完全一样！

2020-03-03