H********h 发帖数: 11 | 1 Given a matrix with each row and column sorted in ascending order. Find the
median in the matrix. (or Kth largest element in the matrix)
I saw this problem in careercup, but I have no idea for the solution. Any
idea? Thanks.
http://www.careercup.com/question?id=4285682
http://www.careercup.com/question?id=6335704 | j********x 发帖数: 2330 | 2 最简单的解法是维护一个queue,首先将最大元素放入;
然后依次从queue中取值,每取一个值需要将其相邻的两个元素放入queue里(queue以
元素的值为key);
取到k为止,很容易发现queue中最多只能有m= MIN(rwo_num, col_num)个元素,总的复
杂度klogm.
这个问题是有更好的解法的:
http://zhiqiang.org/blog/science/computer-science/median-algorithm-of-ordered-matrix.html | i********s 发帖数: 133 | 3 这句话好像有问题:很容易发现queue中最多只能有m= MIN(rwo_num, col_num)个元素。
比如给定一下面一个matrix:
1, 10, 11, 12
2, 20, 21, 22
3, 30, 31, 32
4, 40, 41, 42
如果我们用min_heap,从第一个元素插入开始,min_heap的变化是:
[1]
[2 10]
[3 10 20]
[4 10 20 30]
[11 20 30 40]
[12 20 21 30 40]
显然,它超过了4了。
所以最多的元素个数时n+m?
另外,哪位能share一下那篇paper "Generalized Selection and Ranking: Sorted
Matrices"
SIAM Journal on Computing, 13(1), pp. 14--30, 1984"
【在 j********x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 最简单的解法是维护一个queue,首先将最大元素放入; : 然后依次从queue中取值,每取一个值需要将其相邻的两个元素放入queue里(queue以 : 元素的值为key); : 取到k为止,很容易发现queue中最多只能有m= MIN(rwo_num, col_num)个元素,总的复 : 杂度klogm. : 这个问题是有更好的解法的: : http://zhiqiang.org/blog/science/computer-science/median-algorithm-of-ordered-matrix.html
| E***n 发帖数: 166 | 4 是这样的, 中值只有可能在从左下角到右上角的对角线上,
所以呢,就将对角线的元素排序然后找到中值就可以了。
可以推广到:
最小的肯定是最左边那条从左小脚到右上角的对角线,也就是第一个元素。 1,
最大的肯定是最右下角的那个元素。 42.
第二大的,肯定是在下面那个矩阵的链接A[4,3] and A[3,4]的那个线上,就是41和32
, 然后排序,得出41就是第二大的了。
找到第二大的以后,然后去A[4,2],A[33]A[24]这三个元素里找比第二大的稍小的元素
就得到第三大的了。在下面的例子里,第一大是42,第二大是41,第三大就是40.
素。
【在 i********s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这句话好像有问题:很容易发现queue中最多只能有m= MIN(rwo_num, col_num)个元素。 : 比如给定一下面一个matrix: : 1, 10, 11, 12 : 2, 20, 21, 22 : 3, 30, 31, 32 : 4, 40, 41, 42 : 如果我们用min_heap,从第一个元素插入开始,min_heap的变化是: : [1] : [2 10] : [3 10 20]
| y*****a 发帖数: 221 | 5 找第3大的时候不考虑A[3][4]?
32
【在 E***n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 是这样的, 中值只有可能在从左下角到右上角的对角线上, : 所以呢,就将对角线的元素排序然后找到中值就可以了。 : 可以推广到: : 最小的肯定是最左边那条从左小脚到右上角的对角线,也就是第一个元素。 1, : 最大的肯定是最右下角的那个元素。 42. : 第二大的,肯定是在下面那个矩阵的链接A[4,3] and A[3,4]的那个线上,就是41和32 : , 然后排序,得出41就是第二大的了。 : 找到第二大的以后,然后去A[4,2],A[33]A[24]这三个元素里找比第二大的稍小的元素 : 就得到第三大的了。在下面的例子里,第一大是42,第二大是41,第三大就是40. :
| e**********6 发帖数: 78 | 6 1 1 1 2 3
1 1 1 3 3
1 1 1 3 3
1 1 3 3 3
1 3 3 3 3
的median好像是2吧,不在你所说的对角线上
32
【在 E***n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 是这样的, 中值只有可能在从左下角到右上角的对角线上, : 所以呢,就将对角线的元素排序然后找到中值就可以了。 : 可以推广到: : 最小的肯定是最左边那条从左小脚到右上角的对角线,也就是第一个元素。 1, : 最大的肯定是最右下角的那个元素。 42. : 第二大的,肯定是在下面那个矩阵的链接A[4,3] and A[3,4]的那个线上,就是41和32 : , 然后排序,得出41就是第二大的了。 : 找到第二大的以后,然后去A[4,2],A[33]A[24]这三个元素里找比第二大的稍小的元素 : 就得到第三大的了。在下面的例子里,第一大是42,第二大是41,第三大就是40. :
| i********s 发帖数: 133 | 7 应该不能保证在对角线上。
想到一个nlogn的算法。 |
|