DS-007 顺序表-寻找两个序列的中位数_找出序列a，b的中位数java

作者：黑客灵魂 | 2024-07-03 22:44:56

踩

找出序列a，b的中位数java

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

要求： (1)给出算法的基本设计思想。

(2)根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。

(3)说明你所设计算法的时间复杂度和空间复杂度。

答：

（1）算法思想：将A和B用二路归并合并排序成C，找C的中位数。

根据题目，序列S为奇数，5个元素，下标（0+4）/2=2，刚好第三个元素下标是2。，S的元素个数为偶数10，（0+9）/2 = 4 ，刚好取第5个元素。A、B等长，合并之后元素个数一定是偶数。

（2）C代码：

int Mid_Search(int A[], int B[

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/黑客灵魂/article/detail/784747