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). ｎ是奇数
假设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 的大作中提到】
: 总结的很好啊，谢谢：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 的大作中提到】
: 假设两个有序数组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). ｎ是奇数
: 假设median(A)和median(B)的单median的序号都是m，则问题化归为求
| x******3
发帖数: 245 | 5 同问
【在 y**i 的大作中提到】
: 问一下，不明白，求median为什么变成了求mean？median不是中位数的意思么？
| j**l
发帖数: 2911 | 6 如果有序序列的长度为奇数，则median就是正中间的那个数
如果有序序列的长度为偶数，则median是中间的那两个数，有三种处理：
1. 返回median1和median2
2. 返回median1
3. 返回(median1 + median2) / 2.0
【在 x******3 的大作中提到】
: 同问
| 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 的大作中提到】
: 问一下，不明白，求median为什么变成了求mean？median不是中位数的意思么？
|
|
