在排序行的矩阵中找到第k个最小元素

Question

这是一个面试问题。

在排序的行（但不是排序的列）和行之间没有关系的矩阵中查找第k个最小元素。（第一行和第n行之间没有关系——我们只知道每一行都是按升序排列的）

输入示例如下：

[[1,50,60],
 [20,30,40],
 [2,3,4]]
k = 5

这种情况下的结果是

20

因为20是这个矩阵中第五小的元素。

我首先想到将所有元素添加到minHeap中，然后轮询元素，同时每次迭代从k中减去一个，直到我们得到答案。我还考虑为O（m*n）解决方案实现快速选择，尽管这些解决方案并没有真正利用所有行都按升序排序的事实。

解决这个问题的最佳方法是什么？经过思考，我意识到这似乎是一个“合并k个排序列表”的问题，在找到第k个最小元素后，我们停下来。

谢啦

Answer 1

假设以下情况

[[1,3,4,...10],
[1,3,4,...10],
[1,2,4,...10]]
For k = 4, ans = 2

由于每一行都有相同的开始/结束元素，而且任何两行之间都没有关系，因此如果不使用一些蛮力，很难确定任何有用的信息。最简单的解决方案应该是

1. 对第一行的第一个k元素进行最大堆

与完全暴力相比，这有一些小的改进，但仍然具有时间和空间复杂性。