Java 中合并 K 个排序数组的算法正确吗？

Question

在一次面试中，我被要求编写一个 Java 程序来合并 K 个排序数组。输入如下：

int[][] kSortedArrs = { {1, 5, 6, 8},
                {2, 4, 10, 12},
                {3, 7, 9, 11},
                {13, 14, 15, 16}} ;

我知道合并两个排序数组的解决方案，因此我编写了该方法（mergeSortedArrs）并反复使用它作为该问题的解决方案。代码如下所示：

    public static int[] mergeKSortedArrays(int[][] arr) {
        int[] mergedArr = new int[] {};
        for(int i=0; i < arr.length; i++) {
            mergedArr = mergeSortedArrs(mergedArr, arr[i]);
        }
        return mergedArr;
    }

    private static int[] mergeSortedArrs(int[] arr1, int[] arr2) {
        int[] arr3 = new int[arr1.length + arr2.length];
        int i = 0;
        int j = 0;
        for (int k = 0; k < arr3.length; k++) {
            if (i >= arr1.length) {
                arr3[k] = arr2[j++];
                continue;
            }
            if (j >= arr2.length) {
                arr3[k] = arr1[i++];
                continue;
            }
            arr3[k] = arr1[i] <= arr2[j] ? arr1[i++] : arr2[j++];
        }
        return arr3;
    }

我的代码工作得很好，至少对于给我的测试用例来说是这样。但我想知道这个解决方案在正确性方面是否有任何缺点，因为我在互联网上搜索但找不到与我的这个解决方案接近的解决方案。因此，我有点怀疑我是否搞砸了一些事情。请建议。

Answer 1

您的代码是正确的并解决了问题，但速度很慢。想象一下，您有每个元素k的列表1，您的代码将合并前两个，然后添加第三个，然后是第四个，依此类推，总运行时复杂度为O(k^2).

如果您要对数组进行一次遍历，将第一个与第二个、第三个与第四个等等合并，您最终会得到k/2长度为 的排序列表2，这在 中运行O(k)。再次执行此操作以获取k/4长度列表4等，直到只有一个列表。这在 中运行O(k log k)，速度要快得多。