按排序顺序打印行列排序矩阵中的所有元素。

矩阵是用来表示二维数组的基础数据结构。当处理行列都已排序的矩阵时，我们可以使用多种方法高效地按排序顺序打印所有元素。在本文中，我们将探讨使用 Java 编程语言实现此目标的不同策略。

方法一：扁平化与排序

最简单的方法是将矩阵扁平化为一维数组，然后对该数组进行排序。具体步骤如下：

扁平化矩阵： 逐行遍历矩阵，并将所有元素添加到一个一维数组中。

排序数组： 矩阵扁平化后，应用排序算法（例如，快速排序或归并排序）对数组进行排序。

打印排序后的数组： 遍历排序后的数组并打印元素。

这种方法简单直接，但对于较大的矩阵可能不是最高效的。

输出

在此代码中：

• 我们定义一个二维数组 `matrix`，它代表一个行列排序的矩阵。
• 我们计算矩阵的行数和列数。
• 我们创建一个一维数组 `flattenedArray` 来存储矩阵的元素。
• 我们使用嵌套循环来遍历矩阵，并将其元素扁平化存入 `flattenedArray`。
• 扁平化后，我们使用 `Arrays.sort()` 方法对 `flattenedArray`进行排序。
• 最后，我们遍历排序后的数组并打印其元素。

时间复杂度 : O(n*m) + O((n*m)log(n*m))

遍历二维矩阵的时间为 O(n*m)

对大小为 n*m 的数组进行排序的时间为 O((n*m)log(n*m))

空间复杂度 : O(n*m)

因为我们使用了一个额外的空间来存储从二维矩阵转换来的一维矩阵。

方法二：合并已排序数组

由于矩阵的行和列都已排序，我们可以将每一行视为一个已排序的数组，并将它们合并以得到一个单一的排序数组。

创建一个空的最小堆：初始化一个最小堆（优先队列），并将每一行的第一个元素及其行和列索引插入其中。

提取最小值并插入下一个：重复从堆中提取最小元素，打印它，然后从同一行中插入下一个元素（如果可用）。持续此过程直到堆为空。

输出

在此代码中：

• 逐行遍历矩阵，并将每一行的第一个元素添加到最小堆中。
• 由于自定义了比较器，最小堆会根据节点对应的矩阵值自动组织节点。
• 循环一直持续到最小堆为空，表示所有元素都已打印。
• 在循环的每次迭代中，从最小堆中轮询（poll）并打印最小的元素（堆的根节点）。
• 如果当前节点所在的行还有剩余的列，则将该行的下一个元素添加到堆中以供考虑。

此过程持续进行，直到所有元素都被打印完毕，从而按升序打印出矩阵的元素。

时间复杂度： “合并已排序数组”方法的时间复杂度主要取决于矩阵中的元素总数 (m * n) 和矩阵的行数 (k)。

合并步骤：O(m*n)

优先队列操作：O(m*n * log k)

因此，总体时间复杂度为 O(m*n * log k)，其中 m*n 是矩阵中的元素总数，k 是行数。

空间复杂度： 空间复杂度受用于存储优先队列和其他变量的空间影响。

优先队列：O(k)

其他变量：常数空间

因此，总体空间复杂度为 O(k)，其中 k 是行数。