java - 如何将三个有序数组合并为一个有序数组？在 O(n) 中

Question

我的代码应该选择三个数组并返回三个数组的组合，数组可以有不同的长度。代码应该在 O(n) 内完成组合。

Example: a[] = {1,2} b[] = {1,4,5} c[] = {2,4,5,6}

My result should be: d[] = {1,1,2,2,4,4,5,5,6}

Answer 1

一种方法(我相信还有很多其他方法)是:

根据输入数组长度之和创建输出数组:

int[] output = new int[a.length + b.length + c.length];

为每个输入数组创建一个索引指针:

int aIndex = 0;
int bIndex = 0;
int cIndex = 0;

对输出数组中的每个位置循环一次，并用每个输入数组当前索引处的最小值填充它(检查我们是否没有使用该数组):

for(int outputIndex = 0; outputIndex < output.length; outputIndex++) {
    if (aIndex < a.length
            && (bIndex >= b.length || a[aIndex] <= b[bIndex])
            && (cIndex >= c.length || a[aIndex] <= c[cIndex])) {
        output[outputIndex] = a[aIndex];
        aIndex++;
    } else if (bIndex < b.length
            && (aIndex >= a.length || b[bIndex] <= a[aIndex])
            && (cIndex >= c.length || b[bIndex] <= c[cIndex])) {
        output[outputIndex] = b[bIndex];
        bIndex++;
    } else {
        output[outputIndex] =  c[cIndex];
        cIndex++;
    }
}

编辑:这是我编译和测试的代码:

public class Join {

    public static void main(String[] args) {
        int[] a = {1, 2};
        int[] b = {1, 4, 5};
        int[] c = {2, 4, 5, 6};

        int[] output = new int[a.length + b.length + c.length];

        int aIndex = 0;
        int bIndex = 0;
        int cIndex = 0;

        for(int outputIndex = 0; outputIndex < output.length; outputIndex++) {
            if (aIndex < a.length
                    && (bIndex >= b.length || a[aIndex] <= b[bIndex])
                    && (cIndex >= c.length || a[aIndex] <= c[cIndex])) {
                output[outputIndex] = a[aIndex];
                aIndex++;
            } else if (bIndex < b.length
                    && (aIndex >= a.length || b[bIndex] <= a[aIndex])
                    && (cIndex >= c.length || b[bIndex] <= c[cIndex])) {
                output[outputIndex] = b[bIndex];
                bIndex++;
            } else {
                output[outputIndex] =  c[cIndex];
                cIndex++;
            }
        }
    }
}

在调试器中通过方法末尾的断点进行验证。