题目描述
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m+n))。
示例 1:nums1 = [1, 3]nums2 = [2]中位数是 2.0 示例 2:nums1 = [1, 2]nums2 = [3, 4]中位数是 (2 + 3)/2 = 2.5
解决方法
首先，让我们以一种非常规的方式看到 ’ 中位数 ’ 的概念。那是：
“如果我们将排序后的数组切割成等于两半的等长，则平均数为最大值（lower_half）和最小值（upper_half）的平均值，即紧靠切割的两个数字”。
例如，对于[2 3 5 7]，我们在 3 和 5 之间进行切割：
[2 3 / 5 7]
那么中位数 =（3 + 5）/ 2。请注意，在本文中，我将使用 ’/’ 来表示切割和（数字 / 数字）来表示通过数字进行的切割。对于[2 3 4 5 6]，我们将 4 切割：
[2 3（4/4）5 7]
由于我们把 4 分成两半，所以我们说现在子单元的下部和上部都包含 4。这个概念也导致了正确的答案：（4 + 4）/ 2 = 4。为了方便起见，我们使用 L 来表示切割的左边对应的数字，R 表示切割的右边对应的数字。例如[2 3 5 7]，我们分别有 L = 3 和 R = 5。我们观察到 L 和 R 的索引与数组 N 的长度有下列关系：
N Index of L / R
1 0 / 0
2 0 / 1
3 1 / 1
4 1 / 2
5 2 / 2
6 2 / 3
7 3 / 3
8 3 / 4
不难断定 L =（N-1）/ 2 的指数，并且 R = N / 2。因此，中位数可以表示为
(L + R)/2 = (A[(N-1)/2] + A[N/2])/2
为了准备好两个数组的情况，我们在数字之间添加一些想象的“位置”（表示为#），并将数字视为“位置”。
[6 9 13 18] -> [# 6 # 9 # 13 # 18 #] (N = 4)position index 0 1 2 3 4 5 6 7 8 (N_Position = 9)[6 9 11 13 18]-> [# 6 # 9 # 11 # 13 # 18 #] (N = 5)position index 0 1 2 3 4 5 6 7 8 9 10 (N_Position = 11)
正如你所看到的，不管长度为 N，总有正好 2 * N + 1 的位置。因此，中间切割应该总是在第 N 个位置（基于 0 的位置）进行。在这种情况下，由于 index(L)=(N-1)/ 2 和 index(R)=N/2，我们可以推断
index(L) = (CutPosition-1)/2, index(R) = (CutPosition)/2
现在对于两个数组的情况：
A1: [# 1 # 2 # 3 # 4 # 5 #] (N1 = 5, N1_positions = 11)A2: [# 1 # 1 # 1 # 1 #] (N2 = 4, N2_positions = 9)
类似于单数组问题，我们需要找到一个将两个数组分成两半的切割
“左半部分的任何数字”<=“右半部分的任何数字”。
我们也可以提出以下意见：
共有 2 个 N1 + 2 个 N2 + 2 个位置。因此，在切割的每一边必须有 N1 + N2 的位置，并且直接在切割处有 2 个位置。
因此，当我们在 A2 中的位置 C2 = K 处切割时，A1 中的切割位置必须是 C1 = N1 + N2-k。例如，如果 C2 = 2，那么我们必须有 C1 = 4 + 5 – C2 = 7。
[# 1 # 2 # 3 # (4/4) # 5 #] [# 1 / 1 # 1 # 1 #]
切割完成后，我们会有两个 L 和两个 R。他们是
L1 = A1[(C1-1)/2]; R1 = A1[C1/2];L2 = A2[(C2-1)/2]; R2 = A2[C2/2];
在上面的例子中，
L1 = A1[(7-1)/2] = A1[3] = 4; R1 = A1[7/2] = A1[3] = 4;L2 = A2[(2-1)/2] = A2[0] = 1; R2 = A1[2/2] = A1[1] = 1;
现在我们该如何决定这个切割是否是我们想要的切割？因为 L1，L2 是左边最大的数字，而 R1，R2 是右边最小的数字，所以我们只需要
L1 <= R1 && L1 <= R2 && L2 <= R1 && L2 <= R2
确保下半部分的任何数字 <= 上半部分的任何数字。事实上，因为 L1 <= R1 和 L2 <= R2 是自然保证的，因为 A1 和 A2 是分类的，我们只需要确保：
L1 <= R2 且 L2 <= R1。
现在我们可以使用简单的二分查找来找出结果。
如果我们有 L1> R2，这意味着在 A1 的左半部分有太多的大数字，那么我们必须将 C1 向左移动（即向右移动 C2）。如果 L2> R1，那么 A2 的左半部分有太多的大数字，我们必须将 C2 移到左边。否则，这一切是正确的。在我们找到切割后，可以得出结果为（max（L1，L2）+ min（R1，R2））/ 2;
注意：
由于 C1 和 C2 可以相互确定，我们可以先移动其中一个，然后相应地计算另一个。但是，首先将 C2（较短数组上的一个）移动更为实用。原因是，在较短的数组上，所有位置都可能是中位数的切割位置，但在较长的数组上，左右位置过于靠后的位置对于合法切割根本不可能。例如，[1]，[2 3 4 5 6 7 8]。很显然，2 和 3 之间的切割是不可能的，因为如果你用这种方式进行切割，较短的数组没有那么多元素来平衡 [3 4 5 6 7 8] 部分。因此，要将较长的数组用作第一次切割的基础，必须执行范围检查。在较短的数组上执行操作会更容易，也无需进行任何检查。
唯一的边缘情况是当切割落在第 0(第一个)或第 2N（最后一个）位置时。例如，如果 C2 = 2N2，则 R2 = A2 [2 * N2 / 2] = A2 [N2]，其超出数组的边界。为了解决这个问题，我们可以想象，A1 和 A2 实际上有两个额外的元素，INT_MAX 在 A [-1]和 INT_MAX 在 A [N]。这些添加不会改变结果，但会使实现更容易：如果任何 L 落在数组的左边界之外，则 L = INT_MIN，并且如果有任何 R 落在右边界之外，则 R = INT_MAX。
我知道这不是很容易理解，但所有上述推理最终归结为以下简洁的代码：
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int n1 = nums1.length;
int n2 = nums2.length;
if (n1 < n2)
return findMedianSortedArrays(nums2, nums1); // 确保 nums2 为短数组
int lo = 0, hi = n2 * 2; //
while (lo <= hi) {
int c2 = (lo + hi) >> 1;
int c1 = n1 + n2 – c2;
double L1 = (c1 == 0) ? Integer.MIN_VALUE : nums1[(c1 – 1) / 2];
double L2 = (c2 == 0) ? Integer.MIN_VALUE : nums2[(c2 – 1) / 2];
double R1 = (c1 == n1 * 2) ? Integer.MAX_VALUE : nums1[c1 / 2];
double R2 = (c2 == n2 * 2) ? Integer.MAX_VALUE : nums2[c2 / 2];
if (L1 > R2)
lo = c2 + 1; // 增大 c2，减小 c1，向右移动 c2
else if (L2 > R1)
hi = c2 – 1; // 减小 c2，增大 c1，向左移动 c2
else
return (Math.max(L1, L2) + Math.min(R1, R2)) / 2;
}
return -1;
}
时间复杂度：O(log(min(M,N)))
算法解释原文
原文链接：https://lierabbit.cn/2018/04/…