一道程序设计题，望各位高手指点
有两个数组,均已经按升序排列好,编程序计算这两个数组的中位数
举个例子 数组A:{1,4,6,7,9} B{2,3,5,8} 两数组合并后{1,2,3,4,5,6,7,8,9} 中位数就是中间的那个数: 5
要求时间复杂度O(lgn) 空间复杂度O(1)
[解决办法]
#include <stdio.h>
#define LEN1 5
#define LEN2 4
int main(void)
{
int a[LEN1] = {1,4,6,7,9
};
int b[LEN2] = {2,3,5,8
};
int c = 0;
int j = 0,k = 0;
int i;
float out = 0;
for (i = 0; (i < (LEN1+LEN2) / 2) && (j < LEN1) && (k < LEN2); i++) {// - 1
if (a[j] > b[k]) {
if (i == (LEN1+LEN2) / 2 - 1) {
c = b[k];
}
k++;
} else {
if (i == (LEN1+LEN2) / 2 - 1) {
c = a[j];
}
j++;
}
}
if (i == (LEN1+LEN2) / 2) {
if ((LEN1+LEN2) % 2 == 1) {
out = (a[j] < b[k])? a[j]:b[k];
} else {
out = (c + ((a[j] < b[k])? a[j]:b[k])) / 2.0;
}
} else if (j == LEN1) {
k = (LEN1+LEN2) / 2 -i -1;
if ((LEN1+LEN2) % 2 == 1) {
out = b[k + 1];
} else {
out = (b[k] + b[k + 1]) / 2.0;
}
} else if (k == LEN2) {
j = (LEN1+LEN2) / 2 -i -1;
if ((LEN1+LEN2) % 2 == 1) {
out = a[j + 1];
} else {
out = (a[j] + a[j + 1]) / 2.0;
}
}
printf( "out %f\n ",out);
getchar();
return 0;
}
不知道符不符合题意，你试试吧，我没有测试所有的情况，如果出错了，自己改一下
[解决办法]
我想到一种算法，供参考。
设A、B的长度分别为La,Lb，显然La+Lb = n。不失一般性，设La> =Lb。此时设A、B的中位数分别是Ma，Mb。
1、在Lb中查找Ma（如果没有，定位到其左边 <Ma，右边> Ma的地方），因为Lb是已经排序的，所以可以二分查找，其时间复杂度为lg(Lb) <=lg(n/2)
2、如果Ma恰好等于Mb，或者距离Mb不大于一个常数K（注意这个常数是不依赖于n的，哪怕你取得很大如100万，1000万，但当n更大的多时，它仍然是渺小的；这个常数是为了提高效率，避免在递归到总长度很小时的不必要开销。在最一般的情况下，可以设K为0），则问题已经解决（之后复杂度是K的线形函数，因为K是一个常数，所以只有O(1)，并且它是trivial的，略过不谈）
3、否则，Ma在Mb的左边或右边。不失一般性，设Ma在Mb的左边。此时（注意了，这里是关键！），Lb中Ma左边的元素以及La中Ma及其左边的元素可以排除，因为它们并不包含中位数!!所以，排除这些数。
4、设排除的数总共有s个，显然s > = La/2 > = n/4 。此时问题发生了一些变化：原来是查找n个数中的中位数，现在是查找剩下n-s个元素中先排除最大的s个数后的中位数。简单的说，在右边还欠了s个数需要排除。
5、设经过上一轮后，剩下的数组为C，D，长度分别为Lc,Ld(显然第一轮后Lc + Ld = n-s）。不失一般性，设Lc> =Ld。同样的，求出C的中位数Mc，并查找它在D中的位置。此时仍然是让它与D中的一个合适位置做比较。但是这个合适位置不是Md了，而是经过s调整的Md '（以第一次排除之后的情形看，Md '是D中左起第n/2 - s - Lc/2 个元素）。同第2步，如果Mc在D中的位置与Md '相差不大于K，则问题已经解决。
6、同第3步，如果Mc在Md '的左边，则删除C、D中Mc左边的值，并调整s的值；否则删除右边的值（注意如果第5步中Md '的位置永远以左起定位，那么s可以表示左边已排除的个数，Md '永远等于n/2-s-Lc/2 ，右边已删除的个数不必另行记录，因为它等于n-Lc-Ld-s），回到第5步继续。
这个算法中，每次至少排除长数组的一半元素，即总长度的1/4，所以性能上还是比较高的。
空间复杂度是O(1)，需要保存的变量包括n、s、Lc、Ld、C、D的当前开始位置、Mc、Md '以及二分查找中的变量等等，是与n无关的有限个变量
时间复杂度则有一些难度。不过至少可以找到这样一个上限T(n)满足:
T(1) = 0;
T(n) = T(3n/4) + lg(n/2);
这个T(n)不大于O(lgn*lgn)，比线形算法要快。但是是否能达到O(lgn)呢？也许使用比T(n)更精确的方法可以证明此算法能达到O(lgn)。又或者对它做进一步改进，可以达到O(lgn)。
灵光一现的想法，权当抛砖引玉。期待更好的答案。
