m******g
发帖数: 100 | 1 上来就一道median of M sorted array.
以前做过，不过忘了。是不是太弱了。。 |
h*********i
发帖数: 2605 | 2 告他性骚扰
【在 m******g 的大作中提到】
: 上来就一道median of M sorted array.
: 以前做过，不过忘了。是不是太弱了。。
|
m******g
发帖数: 100 | |
l********s
发帖数: 276 | 4 Leetcode 上是两个厘米找median, 现在都是m个里面找median了。看了bar又高了？ |
l********r
发帖数: 221 | 5 leetcode hard题呀，M array中找就更难啦。
是on-site还是店面题目呀？
【在 m******g 的大作中提到】
: 上来就一道median of M sorted array.
: 以前做过，不过忘了。是不是太弱了。。
|
h*********n
发帖数: 11319 | 6 cao 太变态了
【在 m******g 的大作中提到】
: 上来就一道median of M sorted array.
: 以前做过，不过忘了。是不是太弱了。。
|
m******g
发帖数: 100 | |
l********r
发帖数: 221 | 8 三哥就是狠呀，就是想turn down你的节奏。电面有次遇到个三姐 尼玛那个水平差呀，
答得再好她也搞不懂 最好还把我turn down了
【在 m******g 的大作中提到】
: 就是个电话面试。三哥。
|
g****1
发帖数: 6 | 9 是map组的面试吗？如果是的话，我去onsite时候和你碰到过一样的题目，应该是同一
个人
抛开三哥什么不说，我觉得这道题还是挺好的，如果你会从两个array里找到medium，
那从m个里面找我感觉思路其实差不多，而且这题目我个人认为他并不是要你把code写
得bug free，只要写歌大概思路没错应该就可以 |
t*****n
发帖数: 2578 | |
|
|
l********e
发帖数: 103 | 11 请问一下什么思路啊？
【在 g****1 的大作中提到】
: 是map组的面试吗？如果是的话，我去onsite时候和你碰到过一样的题目，应该是同一
: 个人
: 抛开三哥什么不说，我觉得这道题还是挺好的，如果你会从两个array里找到medium，
: 那从m个里面找我感觉思路其实差不多，而且这题目我个人认为他并不是要你把code写
: 得bug free，只要写歌大概思路没错应该就可以
|
a*******g
发帖数: 1221 | 12 这个怎么找？我知道两个里找median的话有类似binary search，leetcode原题。
M怎么找？用个heap？类似merged sort之类的，但估计肯定有更快的。 |
W***o
发帖数: 6519 | 13 把全部lists 放进heap 里头？
: 我靠
: 两个里找我都找不出。m个里咋找？
【在 t*****n 的大作中提到】
: 我靠
: 两个里找我都找不出。m个里咋找？
|
l********n
发帖数: 9 | |
t*****n
发帖数: 2578 | 15 言归正传
m个到底咋做？
2个的leetcode有解答
1个的我自己会二分法
m个的大家教我一下 |
t*********l
发帖数: 566 | 16 我有个算法。。。有点笨哈。。
对整个int 空间binary search
low = -2^31 high = 2^31
将每个mid 的值放到每个array里去binary search，返回最接近的小于它的index， 记
作M_i. 这个过程是M个Log(S_i), S_i 是每个array长度。
将{M_i}加起来，看是否和N／2 相等，N是总的个数。
如果大了， 说明mid对应的值过大，high = mid； 不然，说明mid对应值过小，往右边
找。
32 * M * log(S).
32 是因为，二分找最多32次。
不知道对不对。 |
a**********6
发帖数: 4 | 17 第一步找出m个中位数里面最小的，把最小的那个array删去前一半（中位数肯定不在这
里面），假设删去k个数，现在问题变成找中位-k数；
第二步找每个array里，(中位-k)/m位置上的数，共有m个，这里面最小的，删这个
array一半；
第三步。。。
最后找到中位数
【在 t*****n 的大作中提到】
: 言归正传
: m个到底咋做？
: 2个的leetcode有解答
: 1个的我自己会二分法
: m个的大家教我一下
|
t*****9
发帖数: 569 | 18 我当年被考了道 Median of M un-sorted Arrays。出题的是个老中，还是校友，
转行cs的。见习的是个小中。当时我那个尴尬啊。。
【在 m******g 的大作中提到】
: 上来就一道median of M sorted array.
: 以前做过，不过忘了。是不是太弱了。。
|
f*****i
发帖数: 835 | 19 Unsorted其实简单些，放一起就好了
【在 t*****9 的大作中提到】
: 我当年被考了道 Median of M un-sorted Arrays。出题的是个老中，还是校友，
: 转行cs的。见习的是个小中。当时我那个尴尬啊。。
|
l*3
发帖数: 2279 | 20 这题应该这么做：
对每个array，只需要确认它里面是否有一个元素是median就行，这是简单的，用
binary search做如下的事情：
对于某个待检查的元素，利用binary search找出这M个数组中，每个数组内比它小和比
它大的元素个数，如果是median的话，就必须满足比它小的个数是小于N/2的，而比它
大的是大于N/2的。然后根据个数来判断这个待检查的元素是小了还是大了，这样就可
以在外层循环用binary search来继续判断。
对每个array都做如上的事情，最后总的cost是 O(M * log(N)^2)，其中N是M个数组里
size最大的那个（或者你也可以认为是总的元素个数，这个不会影响asymptotic cost
） |
u****p
发帖数: 526 | 21 三哥估计给他答案也看不懂，专门来黑人的吧
【在 m******g 的大作中提到】
: 就是个电话面试。三哥。
|
