第一种方式：- 由于所有行都已排序，我们可以使用使用最小堆将 M 个数组合并为一个的概念。过程是： - 将每行的第一个元素包含到堆中，删除最小元素并包含删除最小值的行中的下一个元素（第一个最小值将是 matrix[0][0] obv）。做k次，复杂度为O(klogM)
第二种方式：- 在第一种方式中，我没有使用列也已排序的事实。
这里的想法是，当从堆中删除最小元素时，将右侧和底部元素插入堆中（除非它已经在堆中）假设我们的矩阵是：-
5 7 8 9
6 9 10 13
7 11 12 15
8 13 16 17
我知道最小元素是矩阵[0][0]，所以对于 k=1，ans 将是 5 对于 k 大于 1 的值，这是我们想要的，因为 k=1 是微不足道的在第一步，我可以包括 7(0,1) 和 6(1,0) （并使 matrix[0][1]=-1 和 matrix[1][0]=-1 以确保我们稍后知道堆中的哪个元素）进入堆，然后 6(1,0) 将成为第二个最小值。
将添加下一步 9(1,1) 和 7(2,0)。
现在 7(0,1) 将被删除并 8(0,2) 将被添加（ 9(1,1) 已经在堆中，我在矩阵 -1 中输入了这个条目以明确它已经在堆中）。并且以这种方式在每个步骤中删除 1 个元素，最多添加 2 个元素，因此在从堆中删除 k 个这样的元素之后，我们将得到我们的 k 个最小元素。
这里的复杂度是 O(klogk)，因为最多 logk 是堆的高度，我们正在对堆进行 k 次操作，如果我错了，请纠正我。
第二个想法乍一看似乎更好。但是对于 k 大于 M 的情况，
klogk 大于 klogM。
那么是不是 k 小于 M 第二种方法更好，而 k 大于 M 第一种方法更好？现在因为 k 在每一步都在增加，并且高度也在随着 k 越过另一个 2 的幂而增加。
所以我的问题是第二种方法的复杂性是否真的是 O(klogk)？或者通过一些仔细的分析，它是较小的东西？