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

题目描述

给定两个大小为 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/...