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 的大作中提到】
: 最简单的解法是维护一个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 的大作中提到】
: 这句话好像有问题：很容易发现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 的大作中提到】
: 是这样的， 中值只有可能在从左下角到右上角的对角线上，
: 所以呢，就将对角线的元素排序然后找到中值就可以了。
: 可以推广到：
: 最小的肯定是最左边那条从左小脚到右上角的对角线，也就是第一个元素。 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 的大作中提到】
: 是这样的， 中值只有可能在从左下角到右上角的对角线上，
: 所以呢，就将对角线的元素排序然后找到中值就可以了。
: 可以推广到：
: 最小的肯定是最左边那条从左小脚到右上角的对角线，也就是第一个元素。 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的算法。 |
|
