一个长度为L(L≥1)的升序序列S,处在第个位置的数称为s的中位数。例如,若序列S1=(11,13,15,17,19),则Sl的中位数是15,两个序列的中位数是含它们所有元素的升序序列的中位数。例如,若S2=(2,4,6,8,20),则Sl和S2的中位数是

admin2015-12-30  42

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

选项

答案算法的时间复杂度为O(log2n),空间复杂度为O(1)。

解析 综合考查了顺序表的折半查找和归并的思想。
转载请注明原文地址:https://jikaoti.com/ti/eXfjFFFM
0

最新回复(0)