假。

考虑一个像这样的简单矩阵：

1 3 5
2 4 6
7 8 9

9是最大（第9最小）的元素。但是9在A [3，3]和3 + 3！= 9处。（无论您使用什么索引约定，它都不能成立）。

您可以在O（k log n）时间内解决此问题，方法是逐步合并行，并增加堆以有效地找到最小元素。

基本上，您将第一列的元素放入堆中并跟踪它们来自的行。在每一步中，都从堆中删除最小元素，并从其所在的行中推送下一个元素（如果到达该行的末尾，则不进行任何推送）。删除最小值和添加新元素的成本均为O（log
n）。在第j步，您删除了j第 e 个最小的元素，因此，在执行第s步后，k您需要支付总的O(k log n)操作成本（其中n是矩阵中的行数）。

对于上面的矩阵，您首先从1,2,7堆开始。您删除1并添加3（因为第一行是1 3 5）来获取2,3,7。您删除2并添加4以获得3,4,7。删除3并添加5以获得4,5,7。删除4并添加6以获得5,6,7。请注意，我们将按全局排序的顺序删除元素。您会看到，继续此过程将k在k次迭代后产生最小的元素。

（如果矩阵的行多于列，请对这些列进行操作以减少运行时间。）