如何将两个排序数组合并为一个排序数组? [英] 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屋！