算法细节系列（8）：4. Median of Two Sorted Arrays

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434851

4 Median of Two Sorted Arrays

这道题是我在做二分查找题目中最难的一道题，很大一部分原因在于它需要考虑的情况较多，真正理清所有情况，并准确写出答案相当有难度。

问题

Problems:

There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example: 1

nums1 = 1, 3 nums2 = 2 The median is 2.0

Example: 2

nums1 = 1,2 nums2 = 3,4 The median is (2+3) / 2 = 2.5

方案1

有一个很简单的想法，因为这两个数组有序，所以用一个归并算法，合并成一个更大的数组，合并后去求它的中位数们。

public double findMedianSortedArrays(int[] nums1, int[] nums2) {

        int[] array = merge(nums1,nums2);

        if(array.length == 0) return 0;

        int div = array.length / 2;

        if (array.length % 2 == 0)
            return (array[div] + array[div-1]) / 2.0;
        else
            return array[div];
    }



    private int[] merge(int[] nums1, int[] nums2){

        int[] arrays = new int[nums1.length + nums2.length];

        int i = 0, j = 0, k = 0;
        while(i < nums1.length && j < nums2.length){
            if (nums1[i] <= nums2[j]) arrays[k++] = nums1[i++];
            else arrays[k++] = nums2[j++];
        }

        while (i < nums1.length) arrays[k++] = nums1[i++];
        while (j < nums2.length) arrays[k++] = nums2[j++];


        return arrays;
    }

想都不用想，它肯定超时了，时间复杂度为O(n+m)O(n+m)，但可以注意一些地方，如下代码：

int div = array.length / 2;
if (array.length % 2 == 0)
    return (array[div] + array[div-1]) / 2.0;
else
    return array[div];

以下内容参考自https://discuss.leetcode.com/topic/16797/very-concise-o-log-min-m-n-iterative-solution-with-detailed-explanation/3.

判断奇偶性是否需要？举个例子形象点，如求

[1,2 / 3,4]

“/”表示一种划分，所以此时median = (2 + 3) / 2，而对应的下标是1和2。有median = (nums[1] + nums[2]) / 2;再来看看：

[1,2,3,4,5]

这种情况，按照上述代码，下标 = len / 2 = 5 / 2 = 2，所以直接有median = 3。但我们可以表示成median = (3 + 3) / 2，所以假象一个数组，有

[1,2,3 / 3,4,5]

此时对应的下标应该还是为2，有median = (nums[2] + nums[2]) / 2，为了找寻规律我们分别列举长度为1到8，各数组对应中位数的下标，如下：

所以我们可以总结如下规律，寻找中位数的法则为：

(L +　R) / 2= (nums[(N-1)/2] + nums[N/2]) / 2

这样的一个好处在于把奇偶性的判断合并在了一块，其中N表示数组的长度，L表示划分的左元素，R表示划分的右元素。

所以上述代码可以优化成：

int N = arrays.length();
return (arrays[(N-1)/2] + arrays[N/2]) / 2.0;

是不是简洁很多，更重要的是这小技巧能有效的运用在后续的优化方案中。一个很明显的好处在于，这种形式能够减少很多不必要的情况判断。

方案2

到这里，我很难找出优化的点在何方，目的是为了找中位数们，但貌似两数组的有序性用在了merge()方法上，而我们知道，在有序数组中，查找中位数只需要一次操作！而我们却为了要找两个有序数组的中位数，坏到全部遍历一次！从常数级别到线性级别，仅仅因为把一个大的有序数组划分成了两个有序子数组？

问题出在哪？就拿一个例子来说明，数组[1,2,3,4,5,6,7]，它的中位数在哪？很明显，是4吧，为什么是它？有想过么？因为它有序，在它左侧的都比它小，而在它右侧的都比它大，这就是中位数的定义么？并不是，真正中位数的定义是说，存在一个中位数median,使得以它划分，比它小的数和比它大的数的个数相等。所以考虑如下数组[1,3,2,4,6,5,7]，它的中位数是谁？是不是还是4，没错！这才是优化的关键！我们不需要保持数组全部有序，中位数的定义如果依托于数组的中间位置的划分的话，那么我们只需要保持left_part和right_part的个数相等就可以了。所以有序并不是中位数的充分必要条件，维持【全数组】有序性是冗余的。

这是真正为我们找出中位数的核心思想。解释如下：

不用关注英文那一部分，假设A[i-1]和A[i]是第一个有序数组的两个中位数，而B[j-1]和B[j]是第二个有序数组的中位数，由中位数的定义可知，每个有序数组中的左侧长度和右侧长度是一样的，对吧，ok，那么这两个数组应该怎么合并在一块呢？刚才merge是一种方案，它找中位数是保持全数组的有序性，所以中位数的左侧和右侧长度依然是相等的，我们看看上图的合并，A[0]和B[0]一定要确定有序性么，我们一股脑的放在左侧不就好了？

所以接下来的事情就很简单了！我们假设开始寻找中位数，一个方法就是分别找两个数组的中位数，这样它们的左侧部分的长度之和一定等于右侧部分的长度之后。这是中位数必须要满足的条件，但问题来了，如果第一个数组的中位数小于第二个数组的中位数，而此时第一个数组中位数的右侧部分还有相当多的元素时，这说明真正的中位数可能还在右侧，所以关键来了，第一数组的中位数可以右移一个，而与此同时，第二数组的中位数必须左移一个，保证假设的两个中位数左侧部分和右侧部分的长度始终相等。

这种搜寻的终止条件很明显，只要在移动过程中出现，第一数组的中位数超过第二数组的中位数的情况，就说明找到了符合情况的两数。

上述过程只是为了说明寻找中位数的大致流程，而这离真正写完整AC代码有一定差距，如果对代码细节不感兴趣，以下内容可忽略。接下来，我们会逐步细节深入完成此题的求解。

而且，注意上面那种寻找中位数的过程，它一次移动一个位置，能否利用数组的有序性让它跳跃式的搜索呢，也就是我们的二分搜索，这是可以的，如果跳过了，我们让它往回跳即可。只要符合

B[j-1] <= A[i] and A[i-1] <= B[j]

我们让候选的这四个中位数相互约束就好了。为了更好的展示整个过程，我们举个具体的例子。

与其用＃号代替，我们写成如下形式：

[6,9,13,18] - > [6,6,9,9,13,13,18,18,#]

[6,9,11,13,18] - > [6,6,9,9,11,11,13,13,18,#]

这样数组就从原来的长度N，扩展成了2 * N + 1，这样一个好处在于，我在搜索中位数时可以把任何一种划分给搜索到，如当划分cutPosition = 1时，我们得到的位置为index(L) = (cutPosition-1)/2 = 0,index(R) = (cutPosition)/2 = 0，这相当于在原来[6,9,13,18]中，找到了[6/6,9,13,18]的划分。

在看这张图

我们可以得到两个结论：

1. A1数组和A2数组所有的元素个数加起来为2N1 + 2N2 + 2。所以说，另外两个元素就是数组末尾多出来的两个。
2. 为了保证每次划分左右两边的长度相等，所以对于A2的cutPosition = k时，可以立马得到A1数组的cutPosition = N1 + N2 - k，所以如果c2 = 2，c1就必须是4+5-2=7。

而当A2的cutPosition确定后，你会发现它 /左右元素的个数相等（包括’#’）。所以，总结一下，c2的变动会影响c1的变动，但不管怎么变始终保持划分左右部分的元素个数相等。（满足了中位数的定义）

而cutPosition和划分取元素的公式如下：

针对上述例子有：

L1 = A1[(7-1)/2] = A1[3] = 4; R1 = A1[7/2] = A1[3] = 4;

L2 = A1[(2-1)/2] = A2[0] = 1; R2 = A2[2/2] = A2[1] = 1;

现在就是要定义二分查找的几个边界条件了，在上面已经讨论过了，有

L1 <= R1 && L1 <= R2 && L2 <= R1 && L2 <= R2

它们分别是两个数组的左右两个候选中位数，L1 <= R1, L2 <= R2，始终满足条件（两数组有序），所以考虑两种情况来决定搜索方向：

• R2 < L1，这种情况在上面已经说明了，A2数组右半部分还有一部分候选元素，需要让指针向左移lo = mid + 1（注意：指针的变动总是在数组长度较小的数组上，所以我们考虑问题是以R2和L2为中心。）
• L2 > R1，这种就是向右变动更新过头了，所以有hi = mid -1。

注意：指针的变动一定是在数组长度较小的数组上完成，而数组长度大的指针是被动的！防止数组越界。

好了，当满足终止条件后，就仅仅需要分别比较L1,L2,R1,R2的最大最小即可。代码如下：

public double findMedianSortedArrays(int[] nums1, int[] nums2) {

        int N1 = nums1.length;
        int N2 = nums2.length;

        //始终保持变动指针的数组长度最小
        if (N1 < N2) return findMedianSortedArrays(nums2, nums1);
        //边界条件
        if (N2 == 0) return ((double)nums1[(N1-1)/2] + (double)nums1[N1/2])/2;

        int lo = 0, hi = N2 * 2;

        while (lo <= hi){

            int mid2 = (lo + hi) /2;
            int mid1 = N1 + N2 - mid2;

            //注意0和2*N2的边界条件，很巧妙。
            double L1 = (mid1 == 0) ? Integer.MIN_VALUE : nums1[(mid1 - 1)  /2];
            double L2 = (mid2 == 0) ? Integer.MIN_VALUE : nums2[(mid2-1)/2];
            double R1 = (mid1 == N1 * 2) ? Integer.MAX_VALUE : nums1[(mid1)/2];
            double R2 = (mid2 == N2 * 2) ? Integer.MAX_VALUE : nums2[(mid2)/2];

            if (L1 > R2) lo = mid2 + 1;     // A1's lower half is too big; need to move C1 left (C2 right)
            else if (L2 > R1) hi = mid2 - 1;    // A2's lower half too big; need to move C2 left.
            else return (Math.max(L1,L2) + Math.min(R1, R2)) / 2;

        }

        return -1;
    }

简单总结下：

1. 理解中位数的定义在于小于median的个数和大于median的个数相等即可。
2. 天然的有序数组直接找，而当出现两个有序数组找中位数时，始终保持划分的左侧和右侧相等即可。
3. 在搜索时，为了加快搜索速度，需要分别定义L1和R1，L2和R2，利用有序性进行二分查找。
4. 为了能够划分每个元素，假想扩容数组，省去了很多麻烦的边界条件。

高，实在是高。