难度 Hard
主题 分治算法
There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
Example 1:
nums1 = [1, 3]
nums2 = [2]
The median is 2.0
Example 2:
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5
将两个数组合并后，求其中位数。
假设两个数组的长度分别是 m 和 n ，它们的数组长度之和为 k 。本题的意思就是在合并的数组中找 k/2 个数。
如果 k 是偶数，那么就是 k / 2 ； 如果 k 是奇数，那么就是 k / 2 与 k / 2 + 1 的均值。
先来说说 k 是奇数的情况， k 是偶数的情况同理。
如果 a 数组里里面第 k/2 个数比 b 数组里面的大，这说明我们要找的数一定不在 b 的 前 k/2 个元素里。
我们使用反证法证明。 假设 a 、b的长度都是 1000, 那么 k = 2000, k/2 = 1000，
a 的 第500个数比 b 的 第500个数大
。如果我们要找的数在 b 的前 500 个数里，那么 a 数组的前 500 个数一定在小于 b 数组的第 500 个数，因为只有这样才能凑齐 1000 个数。跟我们的假设 a 的第 500 个数大于 b 的第500 个数矛盾。同理可以求证，我们要找的数，也不可能在 a 的后 k/2 个数里。
还需要考虑一个特殊情况，当 k/2 已经大于 a 的长度，说明我们要找的数字一定不在 a 里，b 同理。
