用某种算法求中位数
问题描述：
用某种算法求中位数
设X[0:n-1]和Y[0:n-1]为两个数组,每个数组中含有n个已排好序的数.设计一个算法,找出X和Y的2n个数的中位数...分析算法思路,讲的具体点!（我学的是C++……）谢谢了!
答
问题等同于寻找X和Y的2n个数中,第n和n+1大的数.假设X和Y都是升序排列的,最简单的方法就是不断删除两个数组各自首元素的较小者,一直删除 n-1 次,剩下的最小和次小数,就是目标了.但是这个算法的时间复杂度是 O(n) 的.