j**l 发帖数: 2911 | 1 假设两个有序数组A和B,它们的长度都为n
1. n = 1
median是(A[0] + B[0]) / 2.0
2. n = 2
median是(max(A[0], B[0]) + min(A[1], B[1])) / 2.0
3. n > 2
假如median(A) == median(B), 则median(A+B)就是median(A)或median(B)
假如median(A) != median(B), 不妨设median(A) < median(B),则
1). n是奇数
假设median(A)和median(B)的单median的序号都是m,则问题化归为求
A[m..n-1]和B[0..m]的median
2). n是偶数
假设median(A)和median(B)的双median的序号都是m1, m2(m2 = m1 + 1), 则问题化归
为求
a. A[m1..n-1]和B[0..m2]的median
注意不可以化归为求
b. A[m2..n-1]和B[0..m1]的median
举例说明
A = {2, 4, 6, 10}
B = {1, 3, 9, 12}
n | x****r 发帖数: 99 | 2 总结的很好啊,谢谢:P
不过好像有个小问题?
如果 n=2 的时候:
假设数组1是{3, 9} 数组2是{4, 6}
那你的解法里面median = (max(A[0], B[0]) + min(A[1], B[1])) / 2.0 = 6.5
而实际上应该是5
所以n = 2的时候还要讨论一下?
谢谢 | j**l 发帖数: 2911 | 3 (max{3, 4} + min{9, 6}) / 2.0 = (4 + 6) / 2.0 = 5.0
【在 x****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 总结的很好啊,谢谢:P : 不过好像有个小问题? : 如果 n=2 的时候: : 假设数组1是{3, 9} 数组2是{4, 6} : 那你的解法里面median = (max(A[0], B[0]) + min(A[1], B[1])) / 2.0 = 6.5 : 而实际上应该是5 : 所以n = 2的时候还要讨论一下? : 谢谢
| y**i 发帖数: 1112 | 4 问一下,不明白,求median为什么变成了求mean?median不是中位数的意思么?
【在 j**l 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 假设两个有序数组A和B,它们的长度都为n : 1. n = 1 : median是(A[0] + B[0]) / 2.0 : 2. n = 2 : median是(max(A[0], B[0]) + min(A[1], B[1])) / 2.0 : 3. n > 2 : 假如median(A) == median(B), 则median(A+B)就是median(A)或median(B) : 假如median(A) != median(B), 不妨设median(A) < median(B),则 : 1). n是奇数 : 假设median(A)和median(B)的单median的序号都是m,则问题化归为求
| x******3 发帖数: 245 | 5 同问
【在 y**i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 问一下,不明白,求median为什么变成了求mean?median不是中位数的意思么?
| j**l 发帖数: 2911 | 6 如果有序序列的长度为奇数,则median就是正中间的那个数
如果有序序列的长度为偶数,则median是中间的那两个数,有三种处理:
1. 返回median1和median2
2. 返回median1
3. 返回(median1 + median2) / 2.0
【在 x******3 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 同问
| w****l 发帖数: 88 | 7
举个例子,假设两个数组都只剩下2个元素,分别是: 1,4 和2, 5, 那么median
value 就是
(4+2)/2 =3. 不失一般性,假设两个数组剩下的元素分别为: a1, a2, b1, b2。 因
为两个数
组本身都是排号序的,那么必然有: a1 < a2, b1
相等)。 这
个时候如果进行merge, 得到的必定是如下几种情况:
1. a1, a2, b1, b2; (max(A[0], B[0])= b1,min(A[1], B[1])= a2)
2. a1, b1, a2, b2; 依次类推......
3. b1, a1, a2, b2;
4. b1, b2, a1, a2;
这4 种情况总结起来就是: (max(A[0], B[0]) + min(A[1], B[1])) / 2.0.
(本人新手,请轻拍:)
【在 y**i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 问一下,不明白,求median为什么变成了求mean?median不是中位数的意思么?
|
|