[每日一题]4. Median of Two Sorted Arrays

难度 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 同理。

假设数组的长度分别是 m 和 n, 把数组各自分成两个部分，他们的下标分别是 i 和 j ，那么划分后的数组分别是 a[0] ... a[i-1] 和 a[i]...a[m-1] ， b[0]...b[j-1] 和 b[j] ... b[n-1]。在分割数组的时候，我们可以保持 i 自有变动, j 的值始终 i + j = (m + n + 1) / 2 计算出。那么如果找到第一个 i , 使得分割后的数组满足： a[i-1] < b[j] 并且 b[j-1] < a[i]的话，如果我们把 a[0] ... a[i-1] 和 b[0] ... b[j-1] 合并成在一起(称为左边），把 a[i] ... a[m-1] 和 b[j] ... b[n-1] 合并在一起（称为右边），可以观察出左右两边的数组的元素个数几乎一样多（左边会比右边多一个），并且左边的最大元素会比右边的最小元素小，符合 Medium 的定义。那么整体的 medium 数就一定在 左右两边的边界上了。