algorithm - 将行和列排序的二维数组转换为排序的一维数组

Question

给定一个包含 n*n 个元素的二维数组:

• 所有行都已排序
• 所有列都已排序

例如:

1 5 7
2 6 8
3 9 10

将其转换为一维排序数组。有没有比 O(nlog(n)) 更好的解决方案。

Answer 1

嗯，它的复杂度不能低于 n^2，因为您有 n^2 个元素，每个元素至少要检查一次。

执行此操作的算法是标准的 k 向合并，其复杂度为 N log k，其中 N 是要合并的项目总数, k 为序列数。

在您的 n*n 数组中，您有 n*n 个要合并的项目和 n 个序列(即行)。因此，代入上面的等式:

N log k
N = (n*n)
k = n
(n*n) log n

将二维数组转换为排序的一维数组是 n^2 log n。