如何两个排序的数组合并成一个排序的数组？ [英] How to merge two sorted arrays into a sorted array?

问题描述

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

This was asked of me in an interview and this is the solution I provided:

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

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

Is there a more efficient way to do this?

编辑：修正长度方法

推荐答案

一个小的改进，但主要的循环后，您可以使用 System.arraycopy 复制尾巴无论是输入数组，当你到了对方的结束。这不会改变 O（N）性能解决方案的特点，虽然。

A minor improvement, but after the main loop, you could use System.arraycopy to copy the tail of either input array when you get to the end of the other. That won't change the O(n) performance characteristics of your solution, though.

这篇关于如何两个排序的数组合并成一个排序的数组？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！