引言

这是笔者的第一篇公众号文章，思来想去一直没决定好写什么（因为想写的东西太多了。最后决定讲一道我个人觉得很有意思的一道题，那就是LeetCode上大名鼎鼎的Median of Two Sorted Arrays。这道题是一道非常经典并且有相当难度的二分查找问题，彻底理解和实现之后其他二分查找问题相信都会迎刃而解。

题目详情

原题如下：

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)).You may assume nums1 and nums2 cannot be both empty.

翻译如下：有两个有序数组 nums1和 nums2，长度分别为m和n，在最大时间复杂度为 O(log(m+n))的要求下找到将两个数组合并成的有序数组 nums3的中位数。

例子：A=[1,3,8,10,11], B=[2,4,6,7,9], 将两数组有序合并后得到 C=[1,2,3,4,6,7,8,9,10,11]，此时中位数为 (6+7)/2=6.5.

题目分析

初次看到这道题时可能会毫无头绪，只知道肯定用二分查找（因为有个log)，但是并不知道应该二分求解什么对象，很多人会直奔二分求解数组 C的中位数，但是发现构造数组 C需要手动将两个数组合并，这将直接导致我们的时间复杂度达到 O(n)。并且令人头大的是当合并数组C的长度为奇数或者偶数时，中位数的求法甚至都不一样。因此，我们需要另辟蹊径。

我们先来看一下数组C有偶数个元素的情况

我们不妨如上图所示将融合的过程画出来。可以发现，数组C的左半部分（黄色）由数组A的左边一部分(左paritition)和数组B的左边一部分构成，C的右半部分(绿色)由数组A的右边一部分（右partition）和数组B的右边一部分构成。数组A被 partitionA=2分为左partition和右partition，同样，数组B被 partitionB=3分为左partition和右partition。

不难发现， partitionA和 partitionB必须满足以下关系。





partitionA + partitionB == C.Length() / 2






A[partitionA - 1] <= B[partitionB]






B[partitionB - 1] <= A[partitionA]

简单的说就是，A的右partition加上B的右partition必须等于C长度的一半，A左边的最大值必须小于B右边的最小值，同样B左边的最大值必须小于A右边的最小值。

当我们找到满足条件的这一组数时，中位数将等于：



median = [max(A[partitionA-1],B[partitionB-1]) + min(A[partitionA],B[partitionB])] / 2

简单的说就是，取所有左partition的的最大值和所有右partition的的最小值的平均数， 6=max(3,6), 7=max(7,8), 因此中位数为 (6+7)/2=6.5。

因此，只要确定 partitionA或 partitionB 中任意一个值，我们就能推出另外一个值，并且求得中位数!

比方说我们可以选择求 partitionB的值。数组B的长度为5， partitionB可以是0到5的任意一个值，那么我们必须要把正确的值试出来，怎么试呢？我们可以利用数组A和B的有序性进行二分查找！以下迭代将用伪得不能再伪的伪代码来展示（二分查找窗口从 [0,5]开始）。

iteration 1:





start = ;






end = 5;






partitionB = (start + end) / 2 = 2;






partitionA = C.Length() / 2 - 2 = 5 - 2 = 3;

此时我们查看条件是否满足：





A[partitionA - 1] = 8






A[partitionA] = 10






B[partitionB - 1] = 4






B[partitionB] = 6

此时 A[partitionA-1]>B[partitionB], 显然不符合我们上面的不等式，值得注意的是，此时的情况是A数组的左partition的最大值大于B的右partition的最小值，因此我们的partitionB应该向右边移动，也就是说二分查找的窗口将从 [0,5] 变为 [partitionB+1,5]也就是 [3,5]。于是我们开始第二轮迭代。

iteration 2:





start = 3;






end = 5;






partitionB = (start + end) / 2 = 4;






partitionA = C.Length() / 2 - 4 = 5 - 4 = 1;

我们再次查看条件是否满足：





A[partitionA - 1] = 1






A[partitionA] = 3






B[partitionB - 1] = 7






B[partitionB] = 9

发现不等式这次仍然无法满足( B[partitionB-1]>A[partitionA])，可是此时的情况与上一轮不同，此时B数组的左partition的最大值比A数组的右partition的最小值大，因此partitionB应该向左移动。二分查找窗口将从 [3,5]变为 [3,partitionB-1]也就是 [3,3]。于是我们开始第三轮迭代。

iteration 3:





start = 3;






end = 3;






partitionB = (start + end) / 2 = 3;






partitionA = C.Length() / 2 - 2 = 5 - 3 = 2;

查看条件是否满足：





A[partitionA - 1] = 3






A[partitionA] = 8






B[partitionB - 1] = 6






B[partitionB] = 7

这时可以发现所有的左值都小于右值, 也就是说我们已经得了正确的partition！此时求得中位数为 [max(3,6)+min(8,7)]/2=6.5

在上述过程中有一个需要特别注意的边界条件，那就是 partitionB的值为5时， partitionA求得为0，这时 partitionA-1为-1，同理， partitionB的值为0时， partitionA的值为5，超过了数组的最大索引4。这种极限情况如下图所示。

因此，当索引到数组中不存在的元素时，我们要赋值给这个元素一个特殊的值，我们规定：当 A[partitionA-1]不存在时，赋值给其 INTMIN, 因为如果A的左partition不存在，在做比较的时候任何数都可以比它里面的所有元素大。当 A[partitionA]不存在时，赋值给其 INTMAX，此时同理，如果A的右partition不存在，那么做比较的时候任何数都可以比他里面的所有元素小。对B来说同理。

现在我们已经讨论完毕了C数组长度为偶数的情况。那么长度为奇数时如何求得中位数呢？其实答案很简单，如下图所示，只要取 partitionA和 partitionB的最小值即可。

代码

附上完整的C++代码，只需不到三十行，这样一看其实题目并不难（手动狗头

double findMedianSortedArrays(vector<int>& A, vector<int>& B) {    int lenA = A.size();    int lenB = B.size();    if (lenA > lenB) {        return findMedianSortedArrays(B, A);    }    int start = ;    int end = lenA;    while (start <= end) {        int partitionA = (start + end) / 2;        int partitionB = (lenA + lenB) / 2 - partitionA;        int leftA = (partitionA > ) ? A[partitionA - 1] : INT_MIN;        int rightA = (partitionA < lenA) ? A[partitionA] : INT_MAX;        int leftB = (partitionB > ) ? B[partitionB - 1] : INT_MIN;        int rightB = (partitionB < lenB) ? B[partitionB] : INT_MAX;        if (leftA <= rightB && leftB <= rightA) {            if ((lenA + lenB) % 2) {                return min(rightA, rightB);            } else {                return (max(leftA, leftB) + min(rightA, rightB)) / 2.;            }        } else if (leftA > rightB) {            end = partitionA - 1;        } else {            start = partitionA + 1;        }    }    return ;}

总结

这道算法题属于LeetCode中hard级别的题目，难度主要在于确定二分查找对象和极端边界情况的处理。但是一旦将这两点考虑透彻，写代码将如砍瓜切菜一般。

最后祝各位同学面试超常发挥，毕业生找个好工作，想跳槽的人工资翻倍

！！

ITPub博客

直击LeetCode最经典二分法算法题：Median of Two Sorted Arrays

引言

题目详情

题目分析

代码

总结

最新文章