如何实现接收二维数组的mergeAll方法？将二维数组合并为一维有序数组

你已经实现了合并三个有序一维数组的merge3方法，现在要实现mergeAll来合并二维数组中的所有有序一维数组，以下是两种可行的实现方案：

原merge3方法（供参考） #

public static int[] merge3(int[] a, int[] b, int[] c) {

    int aLength = a.length;
    int bLength = b.length;
    int cLength = c.length;
    int [] d = new int[aLength+bLength+cLength];

    int i = 0;//index for a;
    int j = 0;//index for b;
    int k = 0;//index for c;
    int l = 0;//index for new sorted array l.
    for (l = 0; l < d.length; l++) {
        d[l] = i < a.length && (j >= b.length || a[i] < b[j])
                ? (k >= c.length || a[i] < c[k]
                ? a[i++]
                : c[k++])
                : (j < b.length && (k >= c.length || b[j] < c[k])
                ? b[j++]
                : c[k++]);

    }

    return d;
}

方案一：分治递归实现 #

利用分治思想，将二维数组递归拆分为三个子区间，分别合并每个子区间的结果，最后用merge3合并这三个子结果，逻辑和归并排序类似：

import java.util.Arrays;
import java.util.Objects;

public static int[] mergeAll(int[][] arrays) {
    // 处理null输入
    if (arrays == null) {
        return new int[0];
    }
    // 过滤掉数组中的null元素
    int[][] filteredArrays = Arrays.stream(arrays)
                                   .filter(Objects::nonNull)
                                   .toArray(int[][]::new);
    if (filteredArrays.length == 0) {
        return new int[0];
    }
    return mergeAllHelper(filteredArrays, 0, filteredArrays.length - 1);
}

private static int[] mergeAllHelper(int[][] arrays, int start, int end) {
    // 单个数组直接返回副本
    if (start == end) {
        return Arrays.copyOf(arrays[start], arrays[start].length);
    }
    // 两个数组的情况，复用merge3（第三个参数传空数组）
    if (end - start == 1) {
        return merge3(arrays[start], arrays[end], new int[0]);
    }
    // 拆分为三个子区间
    int mid1 = start + (end - start) / 3;
    int mid2 = mid1 + 1 + (end - (mid1 + 1)) / 3;
    // 递归合并每个子区间
    int[] left = mergeAllHelper(arrays, start, mid1);
    int[] middle = mergeAllHelper(arrays, mid1 + 1, mid2);
    int[] right = mergeAllHelper(arrays, mid2 + 1, end);
    // 合并三个子结果
    return merge3(left, middle, right);
}

方案二：迭代合并实现 #

通过列表维护待合并的数组，每次迭代取出最多三个数组合并，直到列表中只剩一个数组：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Objects;

public static int[] mergeAll(int[][] arrays) {
    // 处理null输入
    if (arrays == null) {
        return new int[0];
    }
    // 过滤null数组并转为列表
    List<int[]> list = new ArrayList<>(Arrays.stream(arrays)
                                            .filter(Objects::nonNull)
                                            .toList());
    if (list.isEmpty()) {
        return new int[0];
    }
    // 循环合并直到只剩一个数组
    while (list.size() > 1) {
        List<int[]> tempList = new ArrayList<>();
        // 每次取3个数组合并
        for (int i = 0; i < list.size(); i += 3) {
            int[] a = list.get(i);
            int[] b = (i + 1 < list.size()) ? list.get(i + 1) : new int[0];
            int[] c = (i + 2 < list.size()) ? list.get(i + 2) : new int[0];
            tempList.add(merge3(a, b, c));
        }
        list = tempList;
    }
    // 返回最终合并结果的副本
    return Arrays.copyOf(list.get(0), list.get(0).length);
}

关键说明 #

1. 边界处理：两个方案都处理了null输入、空数组、单个/两个数组的情况，确保鲁棒性。
2. 复用merge3：对于不足三个数组的情况，通过传递空数组给merge3的参数，直接复用已有逻辑，不需要重新编写合并两个数组的代码。
3. 空数组兼容：原merge3方法本身支持空数组输入（空数组的length为0，会被逻辑跳过），因此可以安全传递。

内容的提问来源于stack exchange，提问作者Antonio Safi