两个长度相同有序序列的中位数

本文主要是介绍两个长度相同有序序列的中位数，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

我当时想的第一个简略算法：把两个序列合并后打印第n个元素，不出所料超时了

第二个思路，存储两个序列，然后轮流从两个序列里查找当前最小元素，找到第n个最小元素打印即可，这是个有序序列所以很好找

然后就是书上的二分法思路：

分别取l1,l2的中位数a,b，则并集序列的中位数在a，b之间。

这是显然的，假设a<b，若中位数小于a，在l1中有一半的元素大于a，在l2中有多于一半的元素大于a，则有多于一般的数大于"中位数"，矛盾。

此时去掉l1左边的k个数，再去掉l2右边的k个数，中位数的位置不变，这玩意也好理解，在合并序列的两侧分别去除相同数目的元素，中位数位置不变

然后两个序列就这样不断二分求中位数，直到两个中位数相同，此即并集中位数，或两个取到边界，则较小的是中位数

当两个序列长度不相同时，我脑子不好用没想出来，在这里找到了能看懂的办法，而且用在长度相同序列好像还更简单

https://zhuanlan.zhihu.com/p/79687649

这篇关于两个长度相同有序序列的中位数的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

Java教程