寻找两个有序数组的中位数

难度:困难1

描述

给定两个大小为 mn 的有序数组 nums1 和 nums2

请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))

你可以假设 nums1nums2 不会同时为空。

示例 1

nums1 = [1, 3]

nums2 = [2]

则中位数是 2.0

示例 2

nums1 = [1, 2]

nums2 = [3, 4]

则中位数是 (2 + 3)/2 = 2.5

题解

使用二分法递归实现。

前言

在解决这个问题之前,我们需要了解中位数的作用,在统计学中:

中位数的作用

将一个集合划分为两个长度相等的子集,其中一个子集中的元素总是大于另一个子集中的元素。

算法

理解了上中位数的划分作用,进一步分析就很接近答案了。

首先,让我们在任一位置 iA 划分成两个部分:

          left_A             |        right_A
    A[0], A[1], ..., A[i-1]  |  A[i], A[i+1], ..., A[m-1]

因为 A 中有 m 个元素,所以我们有 m+1 中划分方法(i=0 \sim m),那么有:

len(left\_A)=i,len(right\_A)=m−i

注意:当 i=0 时,left\_A 为空集, 而当 i=m 时, right\_A 为空集。

采用同样的方式,我们在 j 处将 B 划分为两个部分:

          left_B             |        right_B
    B[0], B[1], ..., B[j-1]  |  B[j], B[j+1], ..., B[n-1]

left\_Aleft\_B 放在一个集合,将 right\_Aright\_B 放在另一个集合,这两个集合分别命名为 left\_partright\_part,如下:

          left_part          |        right_part
    A[0], A[1], ..., A[i-1]  |  A[i], A[i+1], ..., A[m-1]
    B[0], B[1], ..., B[j-1]  |  B[j], B[j+1], ..., B[n-1]

那我们可以确定:

  1. len(left\_part)=len(right\_part)
  2. \max(left\_part) \leq \min(right\_part)

我们已经把集合 {A,B} 中的所有元素划分为长度相同的两部分,并且其中一部分中的元素大于另一部分中的元素,要得到:

median=\frac{\max(left\_part) + \min(right\_part)}{2}

需要确保两个条件:

两个条件

  1. i + j = m - i + n - j(或:m - i + n - j + 1

    如果 n \geq m,只需要使 i = 0 \sim m, j = \frac{m + n + 1}{2} - i

  2. B[j-1] \leq A[i] 以及 A[i-1] \leq B[j]

  • 为了简化分析,我假设 A[i-1],B[j-1],A[i],B[] 总是存在,哪怕出现 i=0,i=m,j=0,或是 j=n 这样的临界条件(将在最后讨论如何处理这些临界值)。
  • 为什么n≥m? 由于 0≤i≤mj=\frac{m+n+1}{2}-i,我必须确保 j 不是负数。如果 n<m,那么 j 将可能是负数,而这会造成错误的答案。

所以,我们需要做的是:

[0,m] 中搜索并找到目标对象 i,以使:

\begin{equation} \left\{ \begin{array}{**lr**} B[j-1] \leq A[i] \\ A[i-1] \leq B[j] \end{array} \right. \end{equation} 其中,j = \frac{m + n + 1}{2} - i

接着,可以按照以下步骤进行二叉树查找了:

  1. i_{min}=0,i_{max}=m, 然后开始在 [i_{min}, i_{max}] 中进行搜索。
  2. i = \frac{i_{min}+i_{max}}{2}, j = \frac{m + n + 1}{2} - i
  3. 现在我们有 len(left\_part)=len(right\_part),而且我们只会遇到三种情况:

    • B[j-1] \le A[i]A[j-1] \le B[i]

      这意味着我们找到了目标对象 i,所以可以停止搜索。

    • B[j - 1] > A[i]:

      这意味着 A[i] 太小,我们必须调整 i 以使 B[j-1] \le A[i]

      • i 增大的时候,j 就会减少

        因此 B[j-1] 会减少,而 A[i] 会增大,那么 B[j-1] \le A[i] 就可能被满足。

      • i 减小的时候,j 就会增大

        因此 B[j-1] 会增大,而 A[i] 会减小,那么 B[j-1] \le A[i] 不满足条件。

      所以我们必须增大 i,那么必须将搜索范围调整为 [i+1, i_{max}],因此,设 i_{min}=i+1,转到步骤 2。

    • A[i-1]>B[j]:

      这意味着 A[i-1] 太大,我们必须减小 i 以使 A[i-1] \le B[j]

      也就是说,我们必须将搜索范围调整为 [i_{min},i-1],因此,设 i_{max}=i-1,转到步骤 2。

当找到目标对象 i 时,中位数为:

\begin{equation} \left\{ \begin{array}{**lr**} \max(A[i-1], B[j-1]) &, 当m+n为奇数时\\ \frac{\max(A[i-1], B[j-1])+\min(A[i],B[j])}{2} &, 当m+n为偶数时 \end{array} \right. \end{equation}

现在,让我们考虑这些临界值i=0,i=m,j=0,j=n,此时A[i-1],B[j-1],A[i],B[j] 可能不存在。

我们需要做的是确保 \max(left_{part}) \le \min(right_{part}) 。因此,如果 ij 不是临界值(这就意味着 A[i-1],B[j-1],A[i],B[j] 全部存在),那么我么必须同时检查 B[j-1] \le A[i] 以及 A[i-1] \le B[j] 是否成立。

但是如果 A[i-1],B[j-1],A[i],B[j] 中部分不存在,那么我们只需要检查这两个条件中的一个(或不需要检查)。

举个例子,如果 i=0 ,那么 A[i-1] 不存在,我们就不需要检查 A[i-1] \le B[j] 是否成立。

所以,我们需要做的是在 [0,m] 中搜索并找到目标对象 i,以使:

j=0 \quad or \quad i=m \quad or \quad B[j-1] \le A[i] \\ 或\\ i=0 \quad or \quad j=n \quad or \quad A[i-1] \le B[j],其中 j=\frac{m+n+1}{2}-i

再循环搜索中,我们只会遇到三种情况:

  1. (j=0 \quad or \quad i=m \quad or \quad B[j-1] \le A[i]) 或是 (i=0 \quad or \quad j=n \quad or \quad A[i-1] \le B[j]),这意味着 i 是完美的,我们可以停止搜索。
  2. i>0 \quad and \quad i<m \quad and \quad B[j-1]>A[i] 这意味着 i 太小,我们必须增大它。
  3. i>0 \quad and \quad j<n \quad and \quad A[i-1]>B[j] 这意味着 i 太大,我们必须减小它。

因为:

\begin{equation} \begin{array}{**lr**} m \le n, i<m \Longrightarrow j=\frac{m+n+1}{2}-i>\frac{m+n+1}{2}-m \ge \frac{2m+1}{2}\\ m \le n, i>0 \Longrightarrow j=\frac{m+n+1}{2}-i<\frac{m+n+1}{2} \le \frac{2n+1}{2} \le n \end{array} \end{equation}

所以:

\begin{equation} \begin{array}{**lr**} i<m \Longrightarrow j>0\\ i>0 \Longrightarrow j<n \end{array} \end{equation}

那么情况 2 和情况 3 中,我们不需要检查 j>0 或是 j<n 是否成立。

实现

复杂度分析

  • 时间复杂度:O(\log(\min(m,n)))

    首先,查找的区间是 [0,m],该区间的长度在每次循环之后都会减少为原来的一半,所以,我们只需要执行 \log(m) 次循环。由于我们每次在每次循环中进行常量次数的操作,所以时间复杂度为 O(\log(m))。由于 m \le n,所以时间复杂度是 O(\log(min(m,n)))

  • 空间复杂度:O(1)

    我们只需要恒定的内存来存储 9 个局部变量,所以空间复杂度 O(1)