如何使用“分而治之”策略将每个具有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;
}