如何使用分而治之策略将 k 个排序的数组(每个数组都有 n 个元素)合并为一个包含 k*n 个元素的数组?
到目前为止的理解:我对分而治之的步骤有了一些理解,例如:
将数组列表分成两个列表,每个列表有 k/2 个数组。递归合并 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-Dim 数组作为列表列表传递,并将我的前半部分和后半部分更改为 2 Dim。按照建议排列,但出现错误:“Merge 类型中的方法 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;
}
最佳答案
分而治之的方法是使用递归函数k-way-merge()
,它获取列表列表作为输入,并且在每一步:
- 如果您当前有 1 个数组,则返回它(停止子句)
- 否则,将列表的列表一分为二,并且对于每一半 - 递归调用
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[][]
对象,而不是使用索引来“记住您所在的位置”。
关于algorithm - 合并多个排序数组的分而治之策略,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32219070/