LeetCode04，BAT面试原题，面试题中的难度天花板

作者 | 梁唐

出品 | 公众号：Coder梁（ID：Coder_LT）

大家好，我是梁唐。

一拍脑袋才发现LeetCode系列好久没更新了，我们今天来聊聊LeetCode第四题——寻找两个正序数组的中位数。

在写题解之前，我们先来说一点题外话。

这题在LeetCode中的难度是Hard，由于LeetCode没有对时间限制得非常严，因此实际上它的最优解比Hard还要困难一些。基本上在面试题当中，这道题可以算是天花板级别，老梁纵横面试这么多年，几乎没有见过比这题更难的问题。

因为分享过曾经在面试中被这题卡过十几分钟的经历，老梁还在知乎里被不少人嘲讽，所以今天就和大家好好聊聊这道题，看看它到底难度如何。

题面

这题的题面非常简单，简单到只有一句话：要求两个有序数组的中位数。

我们来看两个示例：

示例 1： 输入：nums1 = [1,3], nums2 = [2] 输出：2.00000 解释：合并数组 = [1,2,3] ，中位数 2 示例 2： 输入：nums1 = [1,2], nums2 = [3,4] 输出：2.50000 解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

分析

首先，我们很容易可以想到最简单的解法， 就是可以先把两个数组归并，归并成一个数组之后，中位数也就水到渠成了。

由于两个数组天然有序，我们在归并的时候都不需要排序，直接采用类似归并排序的操作，可以在O(n)

的复杂度内完成。这样的代码写起来也非常简单，只有几行：

    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size(), m = nums2.size();
        // 往两个数组之后插入最大值，用来在归并时防止下标越界
        nums1.push_back(INT_MAX);
        nums2.push_back(INT_MAX);
        vector<int> merge;
        int i1 = 0, i2 = 0;
        // 归并两个数组
        for (int i = 0; i < n+m; i++) {
            if (nums1[i1] <= nums2[i2]) {
                merge.push_back(nums1[i1++]);
            }else merge.push_back(nums2[i2++]);
        }
        n += m;
        if (n % 2) return merge[n / 2];
        else return (merge[n / 2] + merge[n / 2 - 1]) / 2.0;
    }

这个算法虽然简单，但一样能够通过，耗时也仅有24ms。

如果仅仅是以通过这题为目标的话，那到这里就结束了。但如果我们仔细分析，会发现这样的操作有一个巨大的问题，就是我们额外申请了一个内存，用来存储了两个数组归并之后的结果。

在工程实现当中，这样的做法往往是比较忌讳的，因为内存是很宝贵的，最好不要在函数内部随意开辟大块的内存，往往会影响程序的性能。

另外，在题目描述当中也明确说了，这道题算法的时间复杂度应该为 O(log (m+n)) 。如果在面试当中遇到，那么这样的解法才是正解。

思考

题目当中限制了复杂度，这既是一种限制，其实反过来想也未尝不是一种提示。

通过对问题复杂度估计来反推或者筛选算法，是算法竞赛当中常见的技巧之一。

\log N 级别的算法非常少，因此基本上到这里就可以锁定，这题肯定需要使用二分法。

虽然我们明确了应该使用二分法，但是我们距离解出问题还有很多，仍然有许多问题需要解决。我们一个一个来看。

首先一个问题是，由于我们有两个数组，我们怎么确定答案在哪个数组当中呢？

这个问题并不难，因为只有两个数组A和B，我们完全可以进行穷举，先假设在A数组当中进行寻找，如果找不到那自然答案在B数组。真正的问题是我们如何确定某个值是不是答案呢？换句话说，答案应该满足什么条件呢？

对于这个问题我们可以从题目本身入手，既然是要求中位数，那么这个值自然应该满足中位数的要求。即，在两个数组合并的所有元素当中，排序位于正中。

假设A数组有n个元素，B数组有m个元素，对于某个值x，它在A数组中排名a，在B数组中排名是b。如果x是答案，那么要满足

。

假设我们在A数组当中使用二分法寻找答案，那么对于A数组当中的每个元素，我们都能获得它的下标，它的下标自然就是它在A数组中的排名。所以我们只需要求到它在B数组中的排名，然后判断是否满足中位数的条件即可。

到这里，问题就转化成了，我们怎么样求A数组中的元素在B数组中的排名呢？

当然，我们可以想到可以使用二分法，我们在B数组当中做一下二分，不就行了吗？

实际上我们再深入分析一下会发现，其实并没有必要。因为答案要满足a + b = \frac{n+m}2 ，我们已经知道了a，其实并不一定要求b，我们可以反过来思考，验证一下b = \frac{n+m} 2 - a 是否成立即可。

假设我们要验证A[k]元素是否是答案，如果它是答案，那么它在B数组中的排名应该是\frac{n+m}2 - k-1 ，那么我们把它和B数组中对应位置的元素进行一下比较。

为了书写方便，我们把\frac{n+m}2 - k-1 写成k2，如果B[k2] <= A[k] <= B[k2+1]，说明A[k]在B数组的排名就是我们想要的。如果A[k] < B[k2]，说明我们的k取小了，如果A[k] > B[k2+1]，则说明我们的k取大了。

也就是说我们还是只在A数组当中进行二分，只不过使用了B数组来作为我们二分判断的条件。

但这里只考虑了答案在A数组中的情况，如果答案在B数组里呢？我们当然可以再对B数组进行一次同样的处理，但其实没有必要，我们在考虑A[k]是答案的同时也可以考虑一下B[k2]是答案的可能性。这样，我们就只需要一次操作就可以找到答案了。

LeetCode官方提供了另外一种思路，可能更好理解一些。

我们可以将A数组和B数组都分成两个部分，分界线分别是k1, k2。

A[0], A[1],...A[k1], ... A[n-1]
B[0], B[1],...B[k2], ... B[m-1]

其中k1是A数组的分割点，k2是B数组的分割点，满足k1 + k2 = \frac{n+m} 2 以及A[k1] <= B[k2+1] && B[k2] <= A[k1+1]。也就是说我们把两个数组分成了两个部分，保证两个部分中的元素刚好占一半。

这样中位数只有两种可能：要么是左半边的最大值，要么是左半边最大值和右半边最小值的平均数。

我们仔细分析一下，要同时满足A[k1] <= B[k2+1] && B[k2] <= A[k1+1]这两个条件，本质上就是寻找满足A[k1] <= B[k2+1]的最大的k1。因为只有k1最大时，才能保证B[k2] <= A[k1+1]。

要找满足条件的最大k1，我们同样可以使用二分法来逼近答案。找到了k1之后，k2也就出来了，整理一下就能获得答案。

如果n+m为奇数，那么min(A[k1+1], B[k2+1])就是答案，如果为偶数，那么答案是\frac{max(A[k1], B[k2]) + min(A[k1+1], B[k2+1])}{2} 。

这两个思路本质上是一样的，但我个人感觉官方题解里的思路更容易理解一些。

最后我们来看下代码，这段代码是我写过好几版之后最精简的一版，当中的边界情况非常地多，大家在看代码的时候最好留意一下。

class Solution {
public:
    
    pair<double, double> getValue(vector<int>& nums1, vector<int>& nums2, int pos) {
        // [0, n+1)  n = nums1.size()
        int l = 0, r = nums1.size()+1;
        double med1 = 0, med2 = 0;
        while (l < r) {
            int m = (l + r) >> 1;
            // vi1 = A[k1]，注意k1小于0的情况
            int vi1 = (m == 0 ? INT_MIN : nums1[m-1]);
            // vi2 = A[k1+1]，注意k1+1超界的情况
            int vi2 = (m == nums1.size() ? INT_MAX : nums1[m]);
            // vj1 = B[k2]，注意k2小于0的情况
            int vj1 = (m == pos ? INT_MIN : nums2[pos-m-1]);
            // vj2 = B[k2+1]，注意k2+1超界的情况
            int vj2 = (pos-m == nums2.size() ? INT_MAX : nums2[pos-m]);

            if (vi1 <= vj2) {
                med1 = max(vi1, vj1);
                med2 = min(vi2, vj2);
                l = m + 1;
            }else {
                r = m;
            }
        }
        return make_pair(med1, med2);
    }
    
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        if (nums1.size() > nums2.size()) {
            return findMedianSortedArrays(nums2, nums1);
        }
        int n = nums1.size() + nums2.size();
        if (n % 2) {
            return getValue(nums1, nums2, n >> 1).second;
        }else {
            auto p = getValue(nums1, nums2, n >> 1);
            return (p.first + p.second) / 2.0;
        }
    }
};

题外话

这题的难度很大，尤其是在面试当中遇到，之前如果没有做过的话，想要答出最优解法来并不容易，基本上可以说是面试的天花板了，很少有比这题更难的面试题。

大家不妨将这题看成是一个挑战，可以试试在不看题解的情况下写一下代码。能够把这道题的原理吃透，写出正确整洁的代码，对于我们提升思维和代码能力是非常有好处的。

之后，我将会聚焦在LeetCode以及其他各大公司的面试算法题上来，帮助大家攻克面试环节中的这一难关。希望大家多多支持。