题目链接:https://leetcode.com/problems/median-of-two-sorted-arrays/

题目大意:给定两个有序数组,求合并后的中位数,尝试使用 $O(\log (n_1+n_2))$ 运行时间复杂度的算法求解。

题目要求:

  • 两个数组的长度均在 $[0, 1000]$
  • 合并后数组长度在 $[1, 2000]$
  • 数值范围 $[-10^6, 10^6]$

思路零:Simulation

原本大家可以直观地想到时间复杂度为 $O(n_1+n_2)$ 的线性扫描解法,但是题目强暗示这是一个可用二分搜索解决的问题。比较奇葩的是,排行榜里耗时排在前面的几个解法很多还真是直接 vector 然后 push_back 模拟 Merge 的过程,It works.

只能说数据确实不是很强。

思路一:Binary Search

这道题能够作为 Hard 题的原因是边界条件复杂,需要考虑和分析清楚各种情况。

对于这题存在两个常见的 tricks:

  • 奇偶统一:对长度为 $n$ 的有序数组,其中位数为第 $\frac{n+1}{2}$ 和第 $\frac{n+2}{2}$ 个数取平均;
  • 长短统一:对于传引用的两个数组,为了避免分情况讨论,可使用下面的技巧——

上面的第二个技巧根据情况进行使用,比如我将会在另一个思路中使用到。

简化问题形式

有了第一个技巧,问题变成两个有序数组中求第 $k$ 大元素。为了避免二分搜索的过程中产生对数组的拷贝,通常会使用两个类似指针作用的 intp1p2 来表示数组起点的索引(理解不了这种做法的话,后面也更新了直接拷贝数组的写法)。而二分搜索的本质是每次以折半的效率缩小问题规模,所以我们需要考虑如何通过移动这两个起始位置来达到等效于缩小问题规模的目的。

缩小问题规模

终止条件

  • 当出现 p >= nums.size() 表明对应数组为空,直接返回另一个数组对应第 $k$ 大元素;
  • 当问题规模缩小至 $k=1$ 时,只需要比较 nums1[p1]nums2[p2] 取较小值。

这题二分递归的核心思路是:我们需要对 $k$ 进行二分,每次在数组 nums1nums2 中淘汰掉 $k/2$ 个较小的元素,并移动对应的 p 起点,从而让问题求解规模从 $k$ 变成 $k/2$, 究竟从哪个数组中淘汰其前 $k/2$ 个元素呢?

肯定不能随便取,比如数组 [1,2,3,4][5,6,7,8] 中 $k/2=2$, 如果淘汰了 [5, 6] ,虽然它在 [5,6,7,8] 中是较小的两个,但是在 [1, 2, 3, 4, 5, 6, 7, 8] 中明显不是前 $k$ 个较小元素中的值,这样的处理是错误的。

因为两个数组是有序的,利用不等式传递性,我们可以通过比较 nums1[p1] 的 和 nums2[p2] 作为起始的第 $k/2$ 个元素 minVal1minVal2,取二者较小值那边的数组淘汰,确保淘汰掉的 $k/2$ 个较小的元素在另一个数组中也是小于第 $k/2$ 个元素。在上面的例子中,由于 minVal1 == 2 < minVal2 == 6 , 所以可以保证 [1,2] 是合并后的数组中较小的前 $k$ 个数中的 $2$ 个.

需要考虑的一种情况是:某个数组比较短,可能长度没有 $k/2$, 这个时候只要直接去掉另一个数组的前 $k/2$ 个元素即可。因为在这种情况下,这淘汰的 $k/2$ 个元素中一定没有合并后的第 $k$ 大元素。(由于这个时候短的数组找不到 minVal 下标,为了避免其被淘汰,将其设置为 INT_MAX. 又由于中位数的性质,一定不会存在两个数组长度都小于 $k/2$ 的情况。)

时间复杂度:$O(\log (n_1+n_2))$

空间复杂度:$O(1)$

拷贝数组的写法

数组拷贝会有一些空间和时间上的开销,以及这里用 d = min(n, k/2) 来防止越界。

时间复杂度:$O(\log (n_1+n_2))$

空间复杂度:$O(\log (n_1+n_2))$

思路二:Divide and Conquer + Binary Search

这个思路对初见的萌新来说比较难琢磨,面试的时候能想到思路一就足够,想到这个思路的话可能反而说明你见过原题。

在上面的二分搜索中,我们通过不断地二分淘汰掉 $k/2$ 个元素,从而缩小问题规模,最终将达到一个“划分/切割”的效果——所有被淘汰的元素将小于第 $k$ 个元素,剩下的元素都大于等于第 $k$ 个元素。这个时候我们思考一下中位数的特性:

  • 如果以中位数作为合并数组的切分点,根据定义可知,左边的元素都比它小,右边的元素都比它大。
  • 逆向思考一下,将合并的数组进行了拆分,但得到的两个数组依旧有序。
  • 所以在这两个数组中一定存在着这样的两个切分点,使得左边的元素都比中位数小,右边的元素都比中位数大。假设中位数为 c , 比如 nums1 被切分成 [0 ... l1] 和 [ r1 ... n1) , nums2 被切分成 [0 ... l2][r2 ... n2),自然会有 l1 <= c <= r1 && l2 <= c <= r2 , 但是同时还将会存在这样的性质: l1 <= c <= r2 && l2 <= c <= r1 .
  • 如果合并回去,中位数左边将会是 max(l1, l2) ,右边将会是 min(r1, r2) .

简化讨论的 Trick

  1. 注意中位数同时造成的这个性质:一旦某个数组的切分点确定,另一个数组的切分点也被定下来了,因为切分点两边的元素数量相加是一致的。所以我们尽可能地在长度较短的数组中二分查找切分点,这样处理的时间复杂度是 $O(\log \min (n_1, n_2))$ . (在一开始我们提到了这样的 trick)
  2. 考虑到奇偶性带来的影响,为了统一方便表示切分点,在每个元素两侧引入虚拟 # 元素,如 [1 3 5 7] -> [# 1 # 3 # 5 # 7 #] , 单个元素个数由 n 变成 2 * n + 1 . 两个数组元素和变成 2 * n1 + 2 * n2 + 2 , 除去两个切分点,两边各有 n1 + n2 个数字,所以有 c1 + c2 = n1 + n2 . 注意我们只是在计算时引入了虚拟元素的概念,并没有真正改变数组,而且在计算切分点左右的 lr 时需要还原成在数组中真实的索引,这样做只是为了统一表示。

二分查找切分点

终止条件:所以我们的目的就是找到单个顺序数组中的切分点 c1,这样另一个数组的切分点 c2 也确定下来,再检查是否满足上面的性质 l1 <= r2 && l2 <= r1 ,满足则返回中位数,如果不满足则进行二分搜索:

  • 如果 l1 > r2 , 说明 nums1 左半边的元素切多了,切割点 c1 需要左移;
  • 如果 l2 > r1 , 说明 nums2 左半边的元素切多了,切割点 c1 需要右移(等同 c2 左移);
  • 否则满足条件,可以找到中位数 (max(l1, l2) + min(r1, r2)) / 2 .

注意事项:

  • 较短的数组长度为空时的处理,等于直接求另一个数组中位数(有 Trick);
  • 当切割点在 $0$ 或者 $2n$ 的位置时,将 $l$ 或 $r$ 的值分别赋值为 INT_MININT_MAX ,这样在比较大小做二分时并不会改变正确的切分点的位置。

时间复杂度:$O(\log \min (n_1, n_2))$

空间复杂度:$O(1)$