[LeetCode]两个排序数组的中位数(Median of Two Sorted Arrays)

95次阅读

共计 2891 个字符,预计需要花费 8 分钟才能阅读完成。

题目描述
给定两个大小为 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/…

正文完
 0