一道程序设计题 望各位高手指点
有两个数组,均已经按升序排列好,编程序计算这两个数组的中位数
举个例子 数组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)
[解决办法]
从A和B的头慢慢移，移到n/2处就好
[解决办法]
假设两个数组的长度都是n（这个纯粹是为了好说事儿，其实如果两个数组的长度和为偶数就没有中位数了，呵呵），并且其已知（因为求数组长度本身或许已经是O(n)了），那么要求中位数，可以用类似二分法的算法，其实质是一次运算排除大约一般的可能，或说将答案的范围缩小到原来的一半。算法步骤如下：
分别求数组A和B的中位数的位置（不见得非得在正中，可以偏一个），取出对应的数a和b，比大小。比如说a<b，那么，a左边的数和b右边的数就都不是中位数了，都可以删掉了，如果删掉的数的个数恰好一样多，那么就形成了新的数组A和B了，（其实不一样多也没关系，记住了两遍各去掉多少就可以了），而总长度已经减半了，然后循环就可以了。
[解决办法]
看那题举的例子，两数组合并后的长度应该是个基数，如果两数组合并后的长度为n，
这两个数组的中位数
取出对应的数a和b，比大小。如a大于b,则将取数组b下一个数，如a小取a数组中的，如此反复直到取到的元素数为n/2+1时的元素即是
