APP下载

Python快速查询无序亿级阵列的中位数演算法实现

消息来源:baojiabao.com 作者: 发布时间:2024-05-14

报价宝综合消息Python快速查询无序亿级阵列的中位数演算法实现

中位数定义:对于有限的数集,可以通过把所有元素高低排序后找出正中间的一个作为中位数。如果观察值有偶数个,通常取最中间的两个数值的平均数作为中位数。

​实现思路

随机获取无序阵列中一个元素作为分割元素, 以分割元素为界限,将阵列分割大小阵列两部分。若“小”阵列的长度大于中位数索引值, 则基于“小”阵列继续选取随机值缩小其长度。舍弃比中位数值小的元素, 以减少计算量,相应的中位数索引左移对应长度, 保证相对原始资料索引长度不变。判断无序阵列中该分割元素个数, 若大于新的中位数索引, 则该分割元素就是中位数。若小于则舍弃分割元素, 因此调整中位数的索引值,左移对应长度。对“大""阵列重复上述计算。

​Python实现

测试结果

测试环境

测试结果

同时,由于随机抽取元素,进行计算,算法表现稳定性不是很好。

算法复杂度

若对您有所帮助,欢迎大家评论、留言。

2019-12-16 03:50:00

相关文章