一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 668|回复: 8
收起左侧

[Leetcode] Median of Two Sorted Arrays

[复制链接] |试试Instant~ |关注本帖
billyli8866 发表于 2015-5-30 02:08:55 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
搞了两天都没做出来,真是跪了。。。
stellari 发表于 2015-5-30 12:33:41 | 显示全部楼层
别小看这题。虽然算法原理不见得多复杂,但是其中会有很多的edge case。如果想把这些edge case用if else处理的话,代码的复杂度会大大增加的。

所以,你可以试着合并所有的edge case。

首先,你先把一个数组中的“每一个元素”和“每一个元素旁边的间隔”都看做一个“位置”。那么个N个元素的数组中,会有2N+1个这种位置。如果对于一个排好序的数组来说,你可以在第N个位置切一刀,这样切口两侧的元素肯定一样多,所以,中位数一定在切口的周围。如果这一刀正好切在“间隔”位置,那么切口左右两边的数的平均数即为中位数;如果这一刀正好切在“元素”位置,那么你可以理解为那个元素被切成了两半个,那么取这两半个的平均数,同样也是中位数。综合以上两种情况,一个矩阵的中位数肯定是(A[(N-1)/2] +A[N/2])/ 2,不需要判断数组个数。

这样的思路也可以推广到2个数组的情况。假设A数组有10个元素,即21个位置;B数组有7个元素,即15个位置。我现在一刀把这两个数组切开,那么如果希望中位数在这刀形成的两切口的周围,那么同样必须保证切口左右两边的”位置“数目一样多。例,如果这刀恰通过B数组的第7个位置,那么它也必须通过A数组的第10个位置 。如下图,双竖线表示切口的位置。

1 2 3 4 5 || 6 7 8 9 10
1 1 1 |1| 2 2 2

接下来,还必须进一步保证“两切口左侧的任一元素<=两切口右侧的任一元素”。如何判断这一点?只需保证:

A切口左侧的元素(A左)<=B切口右侧的元素(B右),
和B左< A右

即可。
以上图为例,A切口左右两侧的元素分别是5, 6. B切口左右两侧分别是1, 1 (因为它正好切到了一个元素上)。B左(1) <= A右(6),这点没有问题,但是A左(5) > B右(1),所以表示这种切法是不对的。

那么究竟怎么个不正确法?上面的推理说明A切口左侧依然有大于B中切口右侧的值,说明A中切口太偏右,B中切口太偏左。所以,我们把B中的切口调整到11(用二分法),同时A中的切口也要调整到17-11=6的位置。

此时有

1 2 3 || 4 5 6 7 8 9 10
1 1 1 1 2 |2| 2

B右(2)还是小于A左(3),还是不行,B切口继续向右到13,A切口在17-13=4处
1 2 || 3 4 5 6 7 8 9 10
1 1 1 1 2 2 |2|

此时终于满足切口左侧的元素都小于切口右侧的元素了。此时,中位数一定是两切口左侧两个元素的最大值(max(2,2)=2)和切口左侧两元素的最小值(min(3,2)=2)的平均数。也就是(2 + 2)/2 = 2.

用这种方法,你完全不需要判断数组元素是奇数还是偶数,代码量和普通的二分搜索基本没区别。唯一的特殊情况是,如果某个数组中的切口恰好到了数组的最左边的位置,那么此时”切口左边的数“就不存在了。这时人为地把切口左边的数当做INT_MIN即可。同理如果到了数组最右边,切口右边的数就是INT_MAX。只要两个数组不是都为空,那么切口左边的两个数不可能同时为INT_MIN,切口右边的数也不可能同时为INT_MAX,所以这两个数完全不会影响到最终结果。

我们永远在短的那个数组上做二分法,决定了短数组上切口位置,再确定长的数组的切口位置。为假设B的尺寸为M,A的尺寸为N。那么这个算法的算法复杂度是O(log(min(M, N))

我知道上面说的这些很难很难理解。但是,只要你能理解这个思路,代码会比大部分人的实现短得多。不妨一试。

评分

1

查看全部评分

回复 支持 2 反对 0

使用道具 举报

liutr90 发表于 2015-5-30 05:04:22 | 显示全部楼层
我也是
看了答案也没看懂
回复 支持 反对

使用道具 举报

stellari 发表于 2015-5-30 12:34:00 | 显示全部楼层
别小看这题。虽然算法原理不见得多复杂,但是其中会有很多的edge case。如果想把这些edge case用if else处理的话,代码的复杂度会大大增加的。

所以,你可以试着合并所有的edge case。

首先,你先把一个数组中的“每一个元素”和“每一个元素旁边的间隔”都看做一个“位置”。那么个N个元素的数组中,会有2N+1个这种位置。如果对于一个排好序的数组来说,你可以在第N个位置切一刀,这样切口两侧的元素肯定一样多,所以,中位数一定在切口的周围。如果这一刀正好切在“间隔”位置,那么切口左右两边的数的平均数即为中位数;如果这一刀正好切在“元素”位置,那么你可以理解为那个元素被切成了两半个,那么取这两半个的平均数,同样也是中位数。综合以上两种情况,一个矩阵的中位数肯定是(A[(N-1)/2] +A[N/2])/ 2,不需要判断数组个数。

这样的思路也可以推广到2个数组的情况。假设A数组有10个元素,即21个位置;B数组有7个元素,即15个位置。我现在一刀把这两个数组切开,那么如果希望中位数在这刀形成的两切口的周围,那么同样必须保证切口左右两边的”位置“数目一样多。例,如果这刀恰通过B数组的第7个位置,那么它也必须通过A数组的第10个位置 。如下图,双竖线表示切口的位置。

1 2 3 4 5 || 6 7 8 9 10
1 1 1 |1| 2 2 2

接下来,还必须进一步保证“两切口左侧的任一元素<=两切口右侧的任一元素”。如何判断这一点?只需保证:

A切口左侧的元素(A左)<=B切口右侧的元素(B右),
和B左< A右

即可。
以上图为例,A切口左右两侧的元素分别是5, 6. B切口左右两侧分别是1, 1 (因为它正好切到了一个元素上)。B左(1) <= A右(6),这点没有问题,但是A左(5) > B右(1),所以表示这种切法是不对的。

那么究竟怎么个不正确法?上面的推理说明A切口左侧依然有大于B中切口右侧的值,说明A中切口太偏右,B中切口太偏左。所以,我们把B中的切口调整到11(用二分法),同时A中的切口也要调整到17-11=6的位置。

此时有

1 2 3 || 4 5 6 7 8 9 10
1 1 1 1 2 |2| 2

B右(2)还是小于A左(3),还是不行,B切口继续向右到13,A切口在17-13=4处
1 2 || 3 4 5 6 7 8 9 10
1 1 1 1 2 2 |2|

此时终于满足切口左侧的元素都小于切口右侧的元素了。此时,中位数一定是两切口左侧两个元素的最大值(max(2,2)=2)和切口左侧两元素的最小值(min(3,2)=2)的平均数。也就是(2 + 2)/2 = 2.

用这种方法,你完全不需要判断数组元素是奇数还是偶数,代码量和普通的二分搜索基本没区别。唯一的特殊情况是,如果某个数组中的切口恰好到了数组的最左边的位置,那么此时”切口左边的数“就不存在了。这时人为地把切口左边的数当做INT_MIN即可。同理如果到了数组最右边,切口右边的数就是INT_MAX。只要两个数组不是都为空,那么切口左边的两个数不可能同时为INT_MIN,切口右边的数也不可能同时为INT_MAX,所以这两个数完全不会影响到最终结果。

我们永远在短的那个数组上做二分法,决定了短数组上切口位置,再确定长的数组的切口位置。为假设B的尺寸为M,A的尺寸为N。那么这个算法的算法复杂度是O(log(min(M, N))

我知道上面说的这些很难很难理解。但是,只要你能理解这个思路,代码会比大部分人的实现短得多。不妨一试。

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

oio14644 发表于 2015-6-1 02:07:03 | 显示全部楼层
我也有困惑,当初,参考下面的两个帖子,琢磨出来了,希望对你有所帮助
http://www.cnblogs.com/springfor/p/3861890.html
http://blog.csdn.net/yutianzuijin/article/details/11499917
该方法的核心是将原问题转变成一个寻找第k小数的问题(假设两个原序列升序排列),这样中位数实际上是第(m+n)/2小的数。
所以只要解决了第k小数的问题,原问题也得以解决。

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

aegis 发表于 2015-6-5 20:51:44 | 显示全部楼层
我搞了一上午。。真是感觉被自己蠢哭。。诶,共勉。。
回复 支持 反对

使用道具 举报

思翊要出国 发表于 2015-6-6 08:43:11 | 显示全部楼层
这个题确实属于难题了 我觉得
回复 支持 反对

使用道具 举报

oio14644 发表于 2015-6-8 02:26:24 | 显示全部楼层
思翊要出国 发表于 2015-6-6 08:43
这个题确实属于难题了 我觉得

九章的老师说了,如果之前没做过这个题,面试的时候能有1%的人能做出来就不错了,本来就是非常难的,所以大家不要气馁
回复 支持 反对

使用道具 举报

57656929bb 发表于 2015-6-8 02:33:17 | 显示全部楼层
这题的确是思路很简单但是edge case特别多,我的做法是quickselect的思路,相对较简单一点
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-7 21:16

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表