如何将两个排序的数组合并到一个排序的数组中？[已关闭]

algorithm java big-o mergesort

2022-08-31 06:54:28

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

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

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

编辑：更正了长度方法。

答案 1

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

更紧凑一点，但完全相同！

答案 2

我很惊讶没有人提到这个更酷，更高效和更紧凑的实现：

public static int[] merge(int[] a, int[] b) {
    int[] answer = new int[a.length + b.length];
    int i = a.length - 1, j = b.length - 1, k = answer.length;

    while (k > 0)
        answer[--k] =
                (j < 0 || (i >= 0 && a[i] >= b[j])) ? a[i--] : b[j--];
    return answer;
}

兴趣点

请注意，它执行的操作次数与任何其他 O（n） 算法相同或更少，但在单个 while 循环中以单个语句的形式执行！
如果两个数组的大小大致相同，则 O（n）的常量是相同的。但是，如果数组真的很不平衡，那么版本将获胜，因为在内部，它可以通过单个x86汇编指令来做到这一点。System.arraycopy
请注意，而不是。这保证了“稳定性”，定义为当a和b的元素相等时，我们希望a在b之前的元素。a[i] >= b[j]a[i] > b[j]