首页 > 试题广场 >

试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列

[问答题]

一个长度为 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）说明你所设计算法的时间复杂度和空间复杂度。

城市里的养猫者

（1）给出算法的基本设计思想：
分别求两个升序序列A、 B 的中位数，设为 a 和 b。若 a=b，则 a 或 b 即为所求的中位数；否则，舍弃 a、 b 中较小者所在序列之较小一半，同时舍弃较大者所在序列之较大一半，要求两次舍弃的元素个数相同。在保留的两个升序序列中，重复上述过程，直到两个序列中均只含一个元素时为止，则较小者即为所求的中位数。

（2）算法实现如下：

（3）上述所给算法的时间、空间复杂度分别是 O(log2n)和 O(1)。

发表于 2016-11-19 16:30:45 回复(1)

芒201810182023328

L/2 那五个数，不是第二个数是中位数吗，应该是 (L+1)/2把

发表于 2020-09-10 10:51:55 回复(0)

philian

算法思路：
当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前半段。

发表于 2016-12-16 19:16:11 回复(0)

提交观点

问题信息

递归

上传者：城市里的养猫者

难度：

3条回答 13收藏 3890浏览

试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列

问题信息

热门推荐

相关试题