【中位数问题】两个已升序数组确定其中位数

2023-12-25 13:10:26

题目描述:?

现有两个已升序排列的数组𝐴和𝐵,其规模分别为𝑚和𝑛,试设计一个渐近时间复杂度为𝑂(log(𝑚 + 𝑛))的算法去确定𝐴和𝐵的所有元素的中位数。?

伪码:

伪码解释:?

我们把求中位数的问题转化为求两数组第k小元的问题,同时运用了二分查找来简化时间复杂度。看了网上的视频好像也没有讲得特别清晰,我们还是要结合图去看,因为时间紧张,这里就附上我的草图:

二分查找主要运用的特性就是如果两数组的第k/2个元素都相等,那很明显你们的第k/2个元素都是我的第k小元,但是如果两者不等,那肯定较小的那个和它前面比它小的元素都在我的前k个元素中,我直接把你删去然后让k缩小相同的值,好比找第7个元素,你前3个元素肯定都不是第7个元素,那我直接删去你然后我找剩下数组中的第4个元素即可

这就是我草图的全部,我们现在看第一列:

其实这三步就是我们递归的思路,当我们的k逐级减少到1时,就会到达递归出口。?

文章来源:https://blog.csdn.net/m0_75186846/article/details/135193993
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。