两个有序序列的中位数

深藏阁楼爱情的钟 2022-04-17 00:41 175阅读 0赞

原作者：yanyangjuhua  
原文：[https://blog.csdn.net/yanyangjuhua/article/details/78825603][https_blog.csdn.net_yanyangjuhua_article_details_78825603]

问题：

已知有两个等长的非降序序列S1, S2, 设计函数求S1与S2并集的中位数。有序序列A0,A1,⋯,AN−1的中位数指A(N−1)/2的值,即第⌊(N+1)/2⌋个数（A0为第1个数）。

算法描述：

① 输入两个长度自定且等长的数组，然后对他们进行赋值。算法的思路是分别取他们的中位数进行比较，假设两个数组如下：

1 3 5 7 9

2 3 4 5 6

上面数组的中位数是比下面数组的中位数大的，接下来的操作就是取大中位数的左边（包括中位数），取小中位数的右边（包括中位数）。

1 3 5

4 5 6

再次重复以上操作，最后有

3 5

4 5

接下来已经不能再分别取他们的中位数缩小范围了，所以对两个数组进行比较。取数组的首位进行比较，如上即是3和4进行比较，若是哪边比较小就取它的下一位进行比较。过程就是3和4比（3比4小，所以下标加1）→5和4比（4比5小，所以得到中位数为4）→中位数为4。

这是当数组为奇数长度的情况，若是数组长度为1，或者是数组长度为偶数，要再次进行讨论。

② 当数组长度为1时，比较两个数，谁比较小谁就是中位数。

③ 当数组长度为偶数时，

-100 -10 1 1 1 1

-50 0 2 3 4 5

在第一步，取数组的中位数时候，若是按照奇数的方法，我们会发现，最后取出来的两个数组不是等长的，这样的话就会对我们的实际结果造成影响。如上，我们可以一个数组取第三个数，一个数组取第四个数这样进行比较，这样接下来得到的数组都是等长的。接下来步骤和奇数数组一样。

④ 在这里，偶数数组这样的取法原因是，我们每次取新数组出来，只要两个数组的长度和加起来是原来数组的一半或者大于一半，我们就可以保证中位数一直在我们取出来的新数组里面，不会出现中位数丢失的情况。

算法时间及空间复杂度分析：

时间复杂度：每一次调用的过程为判断余下数组长度是否大于2，接下来判断数组个数是奇数个还是偶数个，最后判断两个数组的中位数谁大谁小。所以t(n) = O(1)+O(1)+O(1)。总共执行次数为logn次。在主函数中，执行的语句为创建两个数组还有数组左右下标等变量，和为数组赋值。所以总的时间复杂度为T(n) = logn\*t(n)+O(n)+O(1) = O(logn)。

空间复杂度：算法中辅助空间并不随着数组长度n而线性增大，所以空间复杂度为O(1)。

[https_blog.csdn.net_yanyangjuhua_article_details_78825603]: https://blog.csdn.net/yanyangjuhua/article/details/78825603