​LeetCode短视频 | 真正O(log(m+n))的解法，那些说归并排序的别误导别人了

了解二分查找和分治算法之后，接下来就做下面第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代码：