我想弄清楚如何合并 2D包含几行大小不均匀的 int 数组，在 Java 中将其放入一个已排序的 1D int 数组中。
例如，如果我的二维数组类似于 [[2, 8], [16, 35], [1, 4], [5, 7, 19]]它会合并成一个已排序的一维数组 [1, 2, 4, 5, 7, 8, 16, 19, 35] .
我的函数的标题看起来像这样，半排序的二维数组和排序的一维数组是参数:
public void mergeTo1D(int[][] sorted, int[] origArray) {
// Code goes here
}
我在这里看到了一些使用最小堆的解决方案，但我不知道如何实现或使用它，因为我刚刚开始学习数据结构。
最佳答案
我相信您可以使用 k-way merge(这是合并排序的概括)。
您在这里拥有的是 n 个排序列表，最大大小为 k。
保留一个包含每个列表中最小元素的最小堆。另外，保留一个结果列表。
然后，每次弹出堆的最小值。让这个数字是 x，并说它是从第 i 行中取出的。将 x 添加到结果列表中，并将第 i 行中的下一个数字添加到最小堆中(如果该数字存在)
重复直到完成所有数组。
复杂性是 O(nklogn) - 考虑到您正在对 n*k 个元素进行排序，并且需要遍历所有元素，因此非常有效。
关于java - 将具有不均匀大小的排序行的二维数组合并为排序的一维数组，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/48982426/