Mor*_*abs 5 java arrays sorting heap mergesort
我试图弄清楚如何将2D包含几行不均匀大小的int数组合并到Java中的一维1D int数组中。
例如，如果我的2D数组是类似的东西[[2, 8], [16, 35], [1, 4], [5, 7, 19]]，它将合并为已排序的1D数组[1, 2, 4, 5, 7, 8, 16, 19, 35]。
我的函数的头看起来像这样，其中半排序的2D数组和1D数组被排序为参数：
public void mergeTo1D(int[][] sorted, int[] origArray) {
// Code goes here
}
我在这里看到了一些使用最小堆的解决方案，但是我不知道如何实现或使用它，因为我才刚刚开始学习数据结构。
小智 0
我相信你可以使用k-way合并（这是合并排序的概括）。
这里有 n 个排序列表，最大大小为 k。保留一个包含每个列表中最小元素的最小堆。另外，保留一个结果列表。
然后，每次弹出堆的最小值。令这个数字为 x，并假设它是从第 i 行获取的。将 x 追加到结果列表中，并将第 i 行中的下一个数字添加到最小堆（如果存在该数字）
重复此操作，直到遍历完所有数组。
复杂度为 O(n k logn) - 考虑到您要对 n*k 个元素进行排序，并且需要遍历所有元素，效率相当高。