了解二分查找和分治算法之后,接下来就做下面第4题号。
题被分类为困难题,但是看完题目之后是有很多解法的,可以用归并排序,也可以用暴力解法。
但是难就难在时间复杂度,它要求是时间复杂度为O(log(m+n)),所以肯定会被用到二分查找。
如果使用归并排序的话时间复杂可能就在O(nlogn)上,远远就超过了二分查找的时间复杂度。
既然要求二分的方法,我们可以考虑这样的思路:
题目要求中位数,两个数组的长度之和除以2等于k。因为有两个数组,k还要再除以2,
得到的数值-1,分别置于两数组对应的下。
两数组都是升序排序,k的值我们要找第k大的数。
9大于3,说明第k大的数不在3的左部分,包括3。
把下面数组前三个数排除掉了,第k大的数变成了第k-3大的数。
也同样5是大于3,上面的数组3左部分排除。以此类推。
关于题目的执行过程,我也制作了短视频,请欣赏!http://mpvideo.qpic.cn/0af2hdozzu4vcbahaudqscqhb4bfbwgmnffmosbuaegq4cqabucq.f10002.mp4?dis_k=8a08df058cb1d34242465ada79291ed6&dis_t=1577420158
然后贴上Java代码: