求多个有序数组的中位数

分别计算A1,A2,,A3的中位数,分别为7,9,11根据关联性,则要寻找的中位数(10)必定满足7<=m<=11从A1,A2,A3中去除小于7,大于11的数,此时各子数组的数据情况如下:

继续计算各子数组的中位数,可的A1:10,A2:9,A3:11,因为此时各数组只剩一个元素,故根据假设可在一起计算其中位数10以10为中心计算lTripCount、rTripCount,经过计算二者相同,根据确定性可断定10为最终的中位数;如果lTreipCount与rTripCount不同,则可推导中位数会落在哪个区间(参考上面的算法描述),从而递归上面的过程

因为每次都根据最小中位数与最大中位数过滤,故每次计算可大约砍掉2/3的数据,算法大约以3n的速度收敛。

总有看腻的时候,不论何等荣华的身份,

求多个有序数组的中位数

相关文章:

你感兴趣的文章:

标签云: