分治策略合并多个已排序数组

Question

如何使用“分而治之”策略将每个具有n个元素的k个已排序数组合并为一个有k * n个元素的单个数组？

目前的理解：我对分而治之的步骤有一定的了解，例如：

将数组列表分成两个列表，每个列表包含k/2个数组。递归地合并2个列表中的数组，最后将结果合并为一个已排序的输出数组。

需要一些思路和帮助！！

public int[] merge(int[][] arrays){
int k = arrays.length;
int n = arrays[0].length;
if size(arrays) == 1:
return arrays.pop()
else
// For longer lengths split the array into two
  int half = arrays.length / 2;
  int[] first_Half = new int[half];
  int[] second_Half = new int[lists.length - half];  
  return merge(merge(first_half),merge(second_half));

---

我尝试将2维数组作为列表的列表传递，并根据建议将第一和第二部分更改为2维数组，但是我遇到了错误：“kWayMerge(List<List>)”方法在kWayMerge方法上不适用于参数（int [][]）。

以下是所做的更改。对于常规合并，我可以使用Arrays.copyOf或clone()方法吗？

// solve the problem separately in each sub-array
            List a = kWayMerge(firstHalf);

// K-merge operation using divide and conquer strategy

     public int[] kWayMerge(List<List>array){ // gets a list of lists as input 
            int[][] firstHalf; int[][] secondHalf;
            if(array.size() == 1) return null; // if currently have 1 array, return it - stop clause
    else {
        int half = array.size()/2;
        firstHalf = new int[half][];
        secondHalf = new int[array.size()-half][];
        // solve the problem separately in each sub-array
        List a = kWayMerge(firstHalf);

    }
     return merge((firstHalf ),(secondHalf));   
}

public int[] merge(int[][] arr1, int[][] arr2) {

    return null;
}

- Ka Mal

---

你的想法很好，是什么阻止了你去实现它呢？ - n. m.

目前我正在尝试测试算法，但在最后一次合并时出现错误，要求将合并方法的参数从二维改为单个维度，然而我想传递二维数组。 - Ka Mal

Answer 1

采用分治法的方法，可以编写一个递归函数k-way-merge()，输入一个列表嵌套列表。在每个步骤中：

• 如果当前只有一个数组，则返回它（停止条件）
• 否则，将列表拆成两半，并对每一半进行递归调用k-way-merge()。合并两个结果列表。

你需要在代码中修改的主要方面是：

  int[] first_Half = new int[half];
  int[] second_Half = new int[lists.length - half];  

在这里，你需要将first_half和second_half转换为int[][]，因为它们实际上是列表的列表。

此外，在最后一行：

return merge(merge(first_half),merge(second_half));

注意，外部的merge()不同，它不是递归调用，而是调用“常规”的merge()，将两个数组合并为一个（由于代码中缺少如何执行此操作的逻辑，因此我假设您已经实现了这样的merge()）。

除此之外，这种方法看起来是正确的，但有点低效，因为您每次迭代都会复制int[][]对象，而不是使用索引“记住您所在的位置”。

- amit

---

@amit，你能否也为这个算法添加一下时间和空间复杂度的解释？ - user5326354