【leetcode】4.寻找两个正序数组的中位数

由于要求要在log(n+m)的时间复杂度内计算出来,故线性合并必然不行,考虑使用二分法。

二分法就是用分治的做法,假设函数 f(rank, a, al, ar, b, bl, br) 代表含义:在a[al, ar)和b[bl, br)区间内第rank小的数字。

则每次分治:am = (al + ar) / 2, bm = (bl + br) / 2 ,

需要计算两个半区间的数字个数:range = (am - al + 1) + (bm - bl + 1),

接下来就是比较a[am]和b[bm]的大小了。

要处理一些边界情况,例如a和b都只剩下一个可以选择的时候,以及a或b没得选的时候

 

-- 热度:58 ℃
-- 于 共写了716个字
-- 文内使用到的标签:

发表评论

电子邮件地址不会被公开。