algorithm - 排序矩阵的选择算法

Question

这是一个谷歌面试问题:

给定一个 N*N 矩阵。所有行都排序，所有列都排序。找到矩阵的第 K 个最大元素。

在 n^2 中做它很简单，我们可以使用堆或合并排序 (n lg n) 对其进行排序，然后得到它，但是有没有更好的方法，比 (n lg n) 更好？

数组示例::

 1   5   7  12
 3   6   8  14
 4   9  10  15
11  17  19  20

1<5<7<12 和 1<3<4<11 与其他行和列类似。现在说我们需要找到第 10 个最小的元素，这里是 11..希望这能为问题增加一些细节......

Answer 1

是的，由于 Frederickson 和 Johnson，有一个 O(K) 算法。

Greg N. Frederickson 和 Donald B. Johnson。 广义选择和排序:排序矩阵。暹罗 J. 计算机。 13，第 14-30 页。 http://epubs.siam.org/sicomp/resource/1/smjcat/v13/i1/p14_s1?isAuthorized=no