logo
Redian新闻
>未名空间
>JobHunting - 待字闺中
>
请教一道google面试算法题
avatar
j*x
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
avatar
i*s
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
avatar
E*n
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]
avatar
y*a
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.
:
avatar
e*6
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.
:
avatar
i*s
7 楼
应该不能保证在对角线上。
想到一个nlogn的算法。
相关阅读
求工业工程内推~版里是不是大部分是软件的?有人面过kWantera吗G 家员工, 你们的股票都能拿全吗上周3晚上file的transfer，怎么现在还没收到receipt？h1b被判什么样子的罪会被遣送回国，失去身份？做 internal tools的组有前途么？G家onsite加面谁能end to end解释下user authentication怎么做提供Google内推湾区公司给PhD 105k是不是太少了WISCONSIN EPIC直接来了40个烙印程序员 (转载)A家电面请问工作中怎么take 电话面试？醉了, google直接给了onsite面试中最重要的是？HR说当天出结果，现在还没消息，是好是坏呀postdoc 算什么hierarchy level?Solution Architect这个职位怎么样？面试请教
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。