终于遇到一题Hard啦!
也许可以好好分析一下。
需要做的是找到两个已经排好序的数组的中位数。
题目大意
首先给的是两个数组nums1
和nums2
。
要求在$O(\log{(m+n)})$的时间内找到这两个数组的中位数。
比如从[1, 2]
和[3]
里面找到2。从[1, 2]
和[3, 4]
里面找到(2 + 3) / 2
。
此外,这两个数组不会同时为空。
解决方案
如果有一个是空的我们就返回另一个的中位数就好了,用二分查找。
那么既然要求log的时间,两个数组也是要一半一半排除的。