用某种算法求中位数设X[0:n-1]和Y[0:n-1]为两个数组,每个数组中含有n个已排好序的数.设计一个算法,找出X和Y的2n个数的中位数...分析算法思路,讲的具体点!（我学的是C++……）谢谢了!

分类: 作业答案 • 2022-07-17 23:40:34

问题描述：

用某种算法求中位数
设X[0:n-1]和Y[0:n-1]为两个数组,每个数组中含有n个已排好序的数.设计一个算法,找出X和Y的2n个数的中位数...分析算法思路,讲的具体点!（我学的是C++……）谢谢了!

答

将X 和 Y 放入数组 Z 中。然后将Z排序，变成一个新的有序数组，
此时取中间那个元素就可以了。

答

问题等同于寻找X和Y的2n个数中,第n和n+1大的数.假设X和Y都是升序排列的,最简单的方法就是不断删除两个数组各自首元素的较小者,一直删除 n-1 次,剩下的最小和次小数,就是目标了.但是这个算法的时间复杂度是 O(n) 的.