查看: 2157|回复: 7
收起左侧

[Leetcode] Median of Two Sorted Arrays

|只看干货
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   88% (299)
 
 
11% (39)    👎

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
搞了两天都没做出来,真是跪了。。。

上一篇:Leetcode 刷题记录!!!不信自己今年找不到工作!!!
下一篇:leetcode网站又挂了
stellari 2015-5-30 12:33:41 | 显示全部楼层
本楼: 👍   100% (6)
 
 
0% (0)   👎
全局: 👍   99% (527)
 
 
0% (5)    👎
别小看这题。虽然算法原理不见得多复杂,但是其中会有很多的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))

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

评分

参与人数 3大米 +11 收起 理由
hongbiao.yang + 3 讲的很清楚!谢谢!
youhaoW + 3 很有用的信息!
laoxie09 + 5 感谢分享!

查看全部评分

回复

使用道具 举报

stellari 2015-5-30 12:34:00 | 显示全部楼层
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   99% (527)
 
 
0% (5)    👎
别小看这题。虽然算法原理不见得多复杂,但是其中会有很多的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大米 +10 收起 理由
创业先锋666 + 10 感谢分享!

查看全部评分

回复

使用道具 举报

liutr90 2015-5-30 05:04:22 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (57)
 
 
0% (0)    👎
我也是
看了答案也没看懂
回复

使用道具 举报

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

评分

参与人数 1大米 +10 收起 理由
创业先锋666 + 10 感谢分享!

查看全部评分

回复

使用道具 举报

aegis 2015-6-5 20:51:44 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   96% (32)
 
 
3% (1)    👎
我搞了一上午。。真是感觉被自己蠢哭。。诶,共勉。。
回复

使用道具 举报

思翊要出国 2015-6-6 08:43:11 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   93% (15)
 
 
6% (1)    👎
这个题确实属于难题了 我觉得
回复

使用道具 举报

无效楼层,该帖已经被删除
57656929bb 2015-6-8 02:33:17 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   83% (584)
 
 
16% (117)    👎
这题的确是思路很简单但是edge case特别多,我的做法是quickselect的思路,相对较简单一点
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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