0

一个长度为 L( L≥1)的升序序列 S, 处在第 L/2个位置的数称为 S 的中位数。例如,若序列 S1=( 11, 13, 15, 17, 19),则 S1 的中位数是 15。两个序列的中位数是含它们所有元素的升序序列的中位数。例如,若 S2=( 2, 4, 6, 8, 20),则 S1 和 S2 的中位数是 11。现有两个等长的升序序列 A 和 B,试设计一个在时间和空间两方面都尽可能高效的算法,找出两个序列 A 和 B的中位数。要求:

(1)给出算法的基本设计思想。 (2)根据设计思想,采用 C 或 C++或 Java 语言描述算法,关键之处给出注释。 (3)说明你所设计算法的时间复杂度和空间复杂度。

回答后才能看到答案和解析
5年前上传
2个回答

算法思路: 当n<3时,可作为递归基,用归并的方法求取合并后的中位数。 考察S1的正向中位数m1=S1[n/2]和S2的逆向中位数m2=S2[(n-1)/2] 如果m1==m2,那么这就是全局的中位数,返回。 如果m1<m2,那么说明:S1前半段和S2前半段都必然不大于m2,S1前半段必定严格小于m2;S1后半段和S2后半段都必然不小于m1,S2后半段必定严格大于m1。这两段,S1前半段和S2后半段,要么和m1或m2同为中位数,要么就绝不会是中位数,因此,直接舍弃,不会影响到中位数的选取,从而缩减问题规模。 同理如果m1>m2,那么舍弃的就是S1后半段和S2前半段。

5年前回答
我的回答