0 点赞 评论 收藏
分享
2017-05-16 19:31
中国人民解放军国防科技大学 C++ 盛夏de午夜: 如果这个数是有范围的比如是int的范围,那就可以二分数的范围来查找。
1.那么可以假设用 (int最大值+int最小值)/2,作为假设中位数mid。
2.对于k个数组,均去查找mid所对应的位置,然后计算所有数组中比mid小和比mid大的数的个数lcont,rcount,因为是有序的,这个过程只要
klogn (n为数组长度)。
3.如果lcount==rcount ,那么mid就是真正的中位数
4.否则继续二分范围,比如lcount大,就让mid往左二分。
总的时间复杂度应该是log(数的范围)*k*logn 。log(数的范围) 一般不大,int的话就32
投递字节跳动等公司10个岗位 >
0 点赞 评论 收藏
分享
关注他的用户也关注了: