LeetCode 4 Median of Two Sorted Arrays

终于遇到一题Hard啦!

也许可以好好分析一下。

需要做的是找到两个已经排好序的数组的中位数。

题目大意

首先给的是两个数组nums1nums2

要求在$O(\log{(m+n)})$的时间内找到这两个数组的中位数。

比如从[1, 2][3]里面找到2。从[1, 2][3, 4]里面找到(2 + 3) / 2

此外,这两个数组不会同时为空。

解决方案

如果有一个是空的我们就返回另一个的中位数就好了,用二分查找。

那么既然要求log的时间,两个数组也是要一半一半排除的。