java - 具有 O(m (log n + log m)) 时间复杂度的算法，用于在每行排序的 n*m 矩阵中查找第 k 个最小元素？

Question

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

We have m*n matrix such that each row is in non-decreasing order (sorted with distinct elements). design an algorithm on order O(m (log m+ log n)) to find k-th smallest element on this matrix (just one element as k-th smallest element).

我认为这是不可能的，所以在谷歌上搜索并找到 this link和 another solution和 this answer to a similar question .
我认为如下:

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

我们在 O(m log n) 中找到该元素的等级.即:在每一行中有多少元素低于在步骤 (1) 中找到的枢轴。

通过比较 k和“枢轴的等级”我们可以知道在每一行中都适用于右半部或左半部。 (减少到 m*n/2 矩阵。)

但是这个算法的时间复杂度是O(m * log^2 n) .什么是可以工作的算法O(m (log n + log m)) ?有什么想法吗？

Answer 1

m - 行
n - 列

您是否需要使用 O(m (log m+ log n)) 的解决方案？复杂？

我能想到一个复杂的解决方案 O(k * log-m)额外空间为 O(m)

对于这种复杂性，您可以使用修改后的 PriorityQueue(堆)数据结构

class PQObject {
    int value; // PQ sorting happens on this int..
    int m; // And m and n are positions.
    int n;
}

您可以将第一列中的所有值放入优先级队列并开始弹出直到第 k 个最小元素

每次弹出时，在弹出的对象中使用 m 和 n 重新插入行的下一个值。

最终问题归结为在 M 个排序数组中找到第 k 个最小的元素。