Find the K largest element in a sorted M*N array - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

Find the K largest element in a sorted M*N array

Find the K largest element in a sorted M*N array# JobHunting - 待字闺中

m*q2011-07-27 07:07

1 楼

Looks like an old question, but failed to find a better solution than O(klg(
m+n)). Any ideas?
The question is quoted from a comment on ihas1337code website
------
1.Two reverse sorted arrays A and B have been given. such that size of A is
m and size of B is n
You need to find the k th largest sum (a+b) where a is taken from A and b is
taken from B. such that k < m*n It can be done in O(n*n) but i believe it
can be done in a very efficient way. I heard someone say there is a paper
from SODA. It's possible to solve it in O(N), however, it requires very
complex algorithm. I am wondering if you can come up with an NlogN algorithm
first then try O(N). These two problems have been very hot interview
problems from Google, however, not many people can solve it very efficiently
yet. I believe you can do it after I read many posts on your site.
2. Given a N*N Matrix. All rows are sorted, and all columns are sorted. Find
the Kth Largest element of the matrix.

e*s2011-07-27 07:07

2 楼

1. 第一个题好像是用一个max-heap做的，就是每次从heap里pop出一个
pair(a[i]+b[j]),然后将 pair(a[i],b[j+1]) 和pair(a[i+1],b[j]) insert到heap里。
但好像需要check是不是重复的pair(a[i],b[j])已经在heap里了。
为避免重复，必须用个变量J-Max track 目前max-heap中所有pair的最大的j. 如果j
< J_Max, insertpair(a[i+1],b[j])到heap里；如果j = J_Max, 将 pair(a[i],b[j+1
]) 和pair(a[i+1
],b[j]) insert到heap里, update as J_Max = J_Max+1.
原帖在 http://www.mitbbs.com/article_t0/JobHunting/31840297.html
2.第二个题，用一个best first search, 从二维数组左上角开始search.
maintain 一个priority queue (= min_heap 来实现), heap.pop()返回heap的min
element.
(1)初始的时候，将M[0][0]insert到min_heap里，
(2)for (i = 0; i < k-1; i++) {
tmp = heap.pop(); // 假设 tmp 为 m[i][j]
if m[i][j+1]没有被insert到heap 过， heap.insert(m[i][j+1]);
if m[i+1][j]没有被insert到heap 过， heap.insert(m[i+1][j]);
}
return(heap.pop());
思路就是：二维数组左上方的元素最小，然后从左上方开始做best first search, 每
次heap pop out出来的元素必然是递增的。执行操作k-1次之后，第k个从heap里pop
out出来的就是第k大的元素。复杂度 O(klog(k)). 不知道有没有更好的解法。

klg(
is
is
it

【在 m**q 的大作中提到】

: Looks like an old question, but failed to find a better solution than O(klg(
: m+n)). Any ideas?
: The question is quoted from a comment on ihas1337code website
: ------
: 1.Two reverse sorted arrays A and B have been given. such that size of A is
: m and size of B is n
: You need to find the k th largest sum (a+b) where a is taken from A and b is
: taken from B. such that k < m*n It can be done in O(n*n) but i believe it
: can be done in a very efficient way. I heard someone say there is a paper
: from SODA. It's possible to solve it in O(N), however, it requires very

g*i2011-07-27 07:07

3 楼

这个J-Max track array思路很好,但是表现上比hashset会好很多吗?
第二题判断有没有插入过似乎这个J-max就用不上了.

里。
j
+1

【在 e******s 的大作中提到】

: 1. 第一个题好像是用一个max-heap做的，就是每次从heap里pop出一个
: pair(a[i]+b[j]),然后将 pair(a[i],b[j+1]) 和pair(a[i+1],b[j]) insert到heap里。
: 但好像需要check是不是重复的pair(a[i],b[j])已经在heap里了。
: 为避免重复，必须用个变量J-Max track 目前max-heap中所有pair的最大的j. 如果j
: < J_Max, insertpair(a[i+1],b[j])到heap里；如果j = J_Max, 将 pair(a[i],b[j+1
: ]) 和pair(a[i+1
: ],b[j]) insert到heap里, update as J_Max = J_Max+1.
: 原帖在 http://www.mitbbs.com/article_t0/JobHunting/31840297.html
: 2.第二个题，用一个best first search, 从二维数组左上角开始search.
: maintain 一个priority queue (= min_heap 来实现), heap.pop()返回heap的min