小编Sam*_*524的帖子

我最近遇到一个面试问题。

我们有m*n一个矩阵，每行都按非递减顺序排列（按不同元素排序）。设计一种算法，以便O(m (log m+ log n))找到k该矩阵上的第-最小元素（只有一个元素作为k第-最小元素）。

我认为这是不可能的，所以在 Google 上搜索并找到此链接和另一个解决方案以及类似问题的答案。

我认为如下：

1. 将所有行的中位数放入一个数组中，我们找到该数组的中位数O(m)并将其称为枢轴

2. 我们在 中找到该元素的排名O(m log n)。即：每一行中有多少个元素低于步骤（1）中找到的主元。

3. 通过比较k和“枢轴的排名”，我们可以知道每一行中的工作在右半部分或左半部分。（简化为m*n/2矩阵。）

但该算法的时间复杂度为O(m * log^2 n)。可以运行的算法是什么O(m (log n + log m))？有什么想法吗？