脸书电面

yogurtland123 · 2017-10-13 08:16:19

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

luka77 · 2017-10-30 13:00:55

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

fredxue · 2017-10-31 03:07:52

jisong_L 发表于 2017-10-13 08:16
如果有 K*N个行。可以分别选出K个中位数。设其中最小的为left，最大的为right，然后每次求mid = (right + l ...

列没排序，怎么对列二分？

siranjoy119 · 2017-10-31 11:00:18

http://www.geeksforgeeks.org/find-median-row-wise-sorted-matrix/

yogurtland123 · 2017-10-31 13:02:23

fredxue 发表于 2017-10-31 03:07
列没排序，怎么对列二分？

每次选出一个数后对每个列进行二分查找，找到比它小的数目，这样一次是 K*logN 改成
每次选出一个数后对每个行进行二分查找，找到比它小的数目，这样一次是 K*logN。

yogurtland123 · 2017-10-31 13:05:47

luka77 发表于 2017-10-30 13:00
为什么第二种方式就能缩小范围？不是很明白，可以详细讲解一下吗？

因为第二种方法起始的right - lef的值t比第一种方法小，这样就会快些了。

luka77 · 2017-10-31 23:12:44

jisong_L 发表于 2017-10-31 13:05
因为第二种方法起始的right - lef的值t比第一种方法小，这样就会快些了。

我就是问第二种方法的right - left为什么会小。假如每一行都是一样，长度比较长，一样的话第二种方法的right-left就比较大了啊。

yogurtland123

luka77 发表于 2017-10-31 23:12
我就是问第二种方法的right - left为什么会小。假如每一行都是一样，长度比较长，一样的话第二种方法的ri ...

You are right. It's up to the inputs.

adrianliu729

这题n*n是偶数的话应该返回什么为median?

iwantanintern

158真的是很奇怪的一道题