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的算法。
相关阅读
人脉和吹牛比刷题重要关于换工作推荐人的问题FB HR说不能negotiate了，是不是真就不能了？每天一发。我们的目标是用刷题绑架所有公司的招聘在哪查美国公司真实工资数据最靠谱？各位看官去发点内推，捞点new grad吧写白板和编译无bug 哪个更难？不管刷不刷题， 能回答下吗unidentified_title30 万包裹比东部的director 还好三番的weebly怎么样？比AA还狠！Amazon竟然停招华人学生！Apple 的 Product Manger 收入怎么样？现在google还是不少人进去的求问G家team match，谢谢30岁了，一年没30万，在弯曲过得好苦逼刷了这么多题 真正遇到的多吗H1b被裁 grace period只剩30天，希望好心人帮帮忙关于换组我争取做到帖子的多样性 这样大家都开心google 每年的RSU refresh 是分48个月vest吗？
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。