在排序矩阵选择算法 [英] Selection algorithms on sorted matrix

问题描述

这是一个谷歌的面试问题：

this is a google interview question :

给出一个N * N矩阵。 所有行进行排序，并且所有列进行排序。 找到该矩阵的第K个最大元素

Given a N*N Matrix. All rows are sorted, and all columns are sorted. Find the Kth Largest element of the matrix.

做在N ^ 2很简单，我们可以使用堆排序或归并排序（N LG N），然后得到它，但有没有更好的办法，比（N LG N）？

doing it in n^2 is simple and we can sort it using heap or merge sort (n lg n) and then get it, but is there a better approach, better than (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..hope这增加了一些细节的问题...

1<5<7<12 and 1<3<4<11 similarly the other rows and columns. now say we need to find the 10th smallest element, in here it is 11..hope this adds some detail to the question...

推荐答案

是的，有一个O（K）的算法，由于弗雷德里克森和约翰逊。

Yes, there is an O(K) algorithm due to Frederickson and Johnson.

格雷格N.弗雷德里克森和唐纳德·约翰逊。 通用选择和排序：排序矩阵的。 SIAM J. COMPUT。 13，第14-30。 http://epubs.siam.org/sicomp /资源/ 1 / smjcat / V13 / I1 / p14_s1？isAuthorized =无

Greg N. Frederickson and Donald B. Johnson. Generalized Selection and Ranking: Sorted Matrices. SIAM J. Comput. 13, pp. 14-30. http://epubs.siam.org/sicomp/resource/1/smjcat/v13/i1/p14_s1?isAuthorized=no

这篇关于在排序矩阵选择算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！