这个题目的比较好的方法是什么？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

这个题目的比较好的方法是什么？

这个题目的比较好的方法是什么？# JobHunting - 待字闺中

c*g2012-02-10 08:02

1 楼

find the median of the two sorted array.
如果两个array长度一样，怎么做比较好？
如果两个array长度不一样，怎么做？
网上查看了一下，但似乎都会有bug啊

i*n2012-02-10 08:02

2 楼

为啥需要care两个array长度是否一样？
找出总长度里面的median不就完了

c*g2012-02-10 08:02

3 楼

怎么做？

【在 i*******n 的大作中提到】

: 为啥需要care两个array长度是否一样？
: 找出总长度里面的median不就完了

e*l2012-02-10 08:02

4 楼

Log(n). 折半找中间的。
性质：2个array一起的median介于各自median的中间
每次比较各自的median，然后各自array去掉一半元素
然后继续。。。

i*e2012-02-10 08:02

5 楼

这题属于那种思路简单，但是写代码不好写。
你可以看看这里的解法：
http://www.leetcode.com/2011/03/median-of-two-sorted-arrays.htm
不过我的解法因为处理 corner case 代码较复杂，你可以看看后面有个读者给出一个
很简洁的解法，就是基于 CLRS 的解法（只能处理两个长度一样的）改变一下。