我正在尝试实现一种算法，以一种简单的方式故意合并 k 个排序 数组(每个数组都有 n 个元素):
步骤:
- 合并第一个和第二个数组
- 将上面的结果数组与第三个数组合并
- 将上面的结果数组与第四个数组合并
- ...依此类推，直到与第 k 个数组合并
我的代码可以输出 3x3、4x4、5x5 2D 数组的排序后的单个数组，但是当 2D 数组变为 6x6 时，它会卡住。
是不是因为代码复杂度太高，导致编译时间太长？或者有一些我不知道的愚蠢的逻辑错误？
我通读了我的代码，我猜问题是我用“<<<==== ??”标记的行。我怎样才能做到正确？
public class Merge {
// merge 2 arrays into a single sorted array
private static int[] merge(int[] arrayA, int[] arrayB) {
int n1 = arrayA.length; // number of elements in arrayA
int n2 = arrayB.length; // number of elements in arrayB
int[] mergeArray = new int[n1+n2];
int i = 0; // pointer of current index in mergeArray
int p1 = 0; // pointer of current index in arrayA
int p2 = 0; // pointer of current index in arrayB
while (p1 < n1 && p2 < n2) {
// put the lowest number the mergeArray until one of the array is done
if (arrayA[p1] < arrayB[p2]) {
mergeArray[i] = arrayA[p1];
i++;
p1++;
}
else if (arrayB[p2] < arrayA[p1]) {
mergeArray[i] = arrayB[p2];
i++;
p2++;
}
}
// if all elements of arrayA is copied to mergeArray, then copy remaining elements in arrayB to it
if (p1 >= n1) {
for (int j = p2; j < arrayB.length; j++) {
mergeArray[i] = arrayB[j];
i++;
}
}
// if all elements of arrayB is copied to mergeArray, then copy remaining elements in arrayA to it
if (p2 >= n2) {
for (int j = p1; j < arrayA.length; j++) {
mergeArray[i] = arrayA[j];
i++;
}
}
return mergeArray;
}
public static int[] naiveMerge(int[][] data) {
int k = data.length; // number of sorted array
int n = data[0].length; // number of elements in each array
int[] resultArray = new int[k*n];
int[] tempArray = Merge.merge(data[0], data[1]); // merge the first two arrays
for (int i = 2; i < k; i++) {
// then merge in the third, fourth ... k arrays
tempArray = Merge.merge(tempArray, data[i]); // <<<==== ??
resultArray = tempArray;
}
return resultArray;
}
}
程序卡住了，如下所示:最后一行“合并后:”之后没有任何显示，但程序仍在运行，直到我强制终止它。
最佳答案
如果您查看 3、4 和 5 的数组，您会发现所有数组中的所有值都是唯一的，这纯属巧合。但是，在您的 6 示例中，请注意存在重复的值(有两个 46)。跟踪 merge 中的第一个 while 循环。如果两个数组在某个时刻碰巧具有相同的值，会发生什么？
祝你好运!
关于java - 合并 k 数组的简单方法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/38799417/