Java教程

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

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

我当时想的第一个简略算法:把两个序列合并后打印第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

 

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