寻找两个正序数组的中位数

1. 题目描述

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数 。

2. 示例

示例 1：

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

示例 2：

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

示例 3：

输入：nums1 = [0,0], nums2 = [0,0]
输出：0.00000

示例 4：

输入：nums1 = [], nums2 = [1]
输出：1.00000

示例 5：

输入：nums1 = [2], nums2 = []
输出：2.00000

提示：

• nums1.length == m
• nums2.length == n
• 0 <= m <= 1000
• 0 <= n <= 1000
• 1 <= m + n <= 2000
• -106 <= nums1[i], nums2[i] <= 106

3. 解题方法

归并法 最容易想到的方法是先合并两个数组，然后从中取中位数，时间复杂度为O(max(m, n))，空间复杂度为O(m+n)

双指针法 对于中位数，我们完全可以有数组长度确定它的位置，维护两个指针，分别指向两个数组的头部，每次将 指向数值较小的指针向后移动一位，如果某一个数组到头，则只需移动另一个数组上的指针，直到到达中位数的位置。 时间复杂度为O(m+n), 空间复杂度为O(1)

二分法 根据中位数的定义，当 $m+n$ 是奇数时，中位数是两个有序数组中的第 $\frac{m+n}{2}+1$ 个元素，当 $m+n$ 是偶数时，中位数是两个有序数组中的第 $\frac{m+n}{2}$ 个元素和第 $\frac{m+n}{2}+1$ 个元素的平均值。因此，这道题可以转化成寻找两个有序数组中的第 $k$ 小的数，其中 $k$ 为 $\frac{m+n}{2}$ 或 $\frac{m+n}{2}+1$

假设两个有序数组分别是 $A$ 和 $B$。要找到第 $k$ 个元素，我们可以比较 $A[\frac{k}{2}-1]$ 和 $B[\frac{k}{2}-1]$ 。由于 $A[\frac{k}{2}-1]$ 和 $B[\frac{k}{2}-1]$ 的前面分别有 $\frac{k}{2}-1$个元素，对于 $A[\frac{k}{2}-1]$ 和 $B[\frac{k}{2}-1]$ 中的较小值，最多只会有 $(\frac{k}{2}-1) + (\frac{k}{2}-1) \le k-2 $ 个元素比它小，那么它就不能是第 $k$ 小的数了，因此这时我们可以舍弃其中较小值之前的元素（包括这个较小值），并重新在余下的两个数组中寻找第 $k-\frac{k}{2}$ 小的元素。

因此存在以下三种情况：

1. 如果 $A[\frac{k}{2}-1] < B[\frac{k}{2}-1]$，则比 $A[\frac{k}{2}-1]$ 小的数最多只有 $A$ 的前 $\frac{k}{2}-1$ 个数和 $B$ 的前 $\frac{k}{2}-1$ 个数，即比 $A[\frac{k}{2}-1]$ 小的数最多只有 $k−2$ 个，因此 $A[\frac{k}{2}-1]$ 不可能是第 $k$ 个数，$A[0]$ 到 $A[\frac{k}{2}-1]$ 也都不可能是第 $k$ 个数，可以全部排除。

2. 如果 $A[\frac{k}{2}-1] > B[\frac{k}{2}-1]$，则可以排除 $B[0]$ 到 $B[\frac{k}{2}-1]$

3. 如果 $A[\frac{k}{2}-1] = B[\frac{k}{2}-1]$，则可以归入第一种情况处理。

有如下三种情况需要特殊处理：

• 如果 $A[\frac{k}{2}-1]$ 或者 $B[\frac{k}{2}-1]$ 越界，那么我们可以选取对应数组中的最后一个元素。在这种情况下，我们必须根据排除数的个数减少 $k$ 的值，而不能直接将 $k$ 减去 $\frac{k}{2}$。

• 如果一个数组为空，说明该数组中的所有元素都被排除，我们可以直接返回另一个数组中第 $k$ 小的元素。

• 如果 $k=1$，我们只要返回两个数组首元素的最小值即可。

此解法时间复杂度为$O(\log_{m+n})$, 空间复杂度为O(1)