LeetCode 算法题：004 求两个有序数组的中位数

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

请求这两个数组的中位数，算法的时间复杂度应该是O(log(m + n))。

你可以假设nums1和nums2不会同时为空。

示例 1：

nums1 = [1, 3]

nums2 = [2]

中位数为

示例 2：

nums1 = [1, 2]

nums2 = [3, 4]

则均值为 (2 + 3)/2 =

演示动画

分析

要求两个有序数组的中位数，我们很容易想到使用方法二分法求有序数组的中位数。时间复杂度为O(log(n))。现在有两个数组，时间复杂度要求是O(log(m+n))，所以和二分法有关。

那么我们如何使用第二个分布来解决这个问题呢？我们进行了进一步的分析。

因为是中位数，所以可以确定这个数的位置：

• 对于m+n为奇数的情况，中位数就是最大数的(m+n)/2。
• 对于m+n为偶数的情况，中位数是(m+n)/2最大数和(m+n)/2+1最大数的平均值。

所以我们可以将上面的问题转化为寻找两个连续数组中第k大的数，k = (m + n) / 2。num1和k2来自num2数组。由于k是一个具体的数字，当k1确定时，k2也确定了。

所以我们可以在nums1数组中选择k1，然后确定nums1数组中的第一个k1数和nums2数组中的第一个k2数是两个数组中最小的部分。规则条件为：

1. nums1[k1 + 1]
2. nums2[k2 + 1]