java - 这个在 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) 中运行。再次执行此操作以获得长度为 4 的 k/4 列表，依此类推，直到只有一个列表。这在 O(k log k) 中运行，速度要快得多。