解决方案

方法：递归法

为了解决这个问题，我们需要理解“中位数的作用是什么”。在统计中，中位数被用来：

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

如果理解了中位数的划分作用，我们就很接近答案了。

首先，让我们在任一位置 ii 将 A\text{A} 划分成两个部分：

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

由于 A\text{A} 中有 mm 个元素， 所以我们有 m+1m+1 种划分的方法（i=0∼mi = 0 \sim m）。

我们知道：

len(left_A)=i,len(right_A)=m−i\text{len}(\text{left\_A}) = i, \text{len}(\text{right\_A}) = m - i.

注意：当 i=0i = 0 时，left_A\text{left\_A} 为空集， 而当 i=mi = m 时, right_A\text{right\_A} 为空集。

采用同样的方式，我们在任一位置 jj 将 B\text{B} 划分成两个部分：

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

将 left_A\text{left\_A} 和 left_B\text{left\_B} 放入一个集合，并将 right_A\text{right\_A} 和 right_B\text{right\_B} 放入另一个集合。 再把这两个新的集合分别命名为 left_part\text{left\_part} 和 right_part\text{right\_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)\text{len}(\text{left\_part}) = \text{len}(\text{right\_part})
  2. max⁡(left_part)≤min⁡(right_part)\max(\text{left\_part}) \leq \min(\text{right\_part})

那么，我们已经将 {A,B}\{\text{A}, \text{B}\} 中的所有元素划分为相同长度的两个部分，且其中一部分中的元素总是大于另一部分中的元素。那么：

median=max(left_part)+min(right_part)2 \text{median} = \frac{\text{max}(\text{left}\_\text{part}) + \text{min}(\text{right}\_\text{part})}{2}

要确保这两个条件，我们只需要保证：

  1. i+j=m−i+n−ji + j = m - i + n - j（或：m−i+n−j+1m - i + n - j + 1） 如果 n≥mn \geq m，只需要使  i=0∼m, j=m+n+12−i \ i = 0 \sim m,\ j = \frac{m + n + 1}{2} - i \\

  2. B[j−1]≤A[i]\text{B}[j-1] \leq \text{A}[i] 以及 A[i−1]≤B[j]\text{A}[i-1] \leq \text{B}[j]

ps.1 为了简化分析，我假设 A[i−1],B[j−1],A[i],B[j]\text{A}[i-1], \text{B}[j-1], \text{A}[i], \text{B}[j] 总是存在，哪怕出现 i=0i=0，i=mi=m，j=0j=0，或是 j=nj=n 这样的临界条件。 我将在最后讨论如何处理这些临界值。

ps.2 为什么 n≥mn \geq m？由于0≤i≤m0 \leq i \leq m 且 j=m+n+12−ij = \frac{m + n + 1}{2} - i，我必须确保 jj 不是负数。如果 n<mn < m，那么 jj 将可能是负数，而这会造成错误的答案。

所以，我们需要做的是：

在 [0，m][0，m] 中搜索并找到目标对象 ii，以使：

B[j−1]≤A[i] \qquad \text{B}[j-1] \leq \text{A}[i]\ 且  A[i−1]≤B[j], \ \text{A}[i-1] \leq \text{B}[j],\ 其中 j=m+n+12−ij = \frac{m + n + 1}{2} - i

接着，我们可以按照以下步骤来进行二叉树搜索：

  1. 设 imin=0\text{imin} = 0，imax=m\text{imax} = m, 然后开始在 [imin,imax][\text{imin}, \text{imax}] 中进行搜索。
  2. 令 i=imin+imax2i = \frac{\text{imin} + \text{imax}}{2}， j=m+n+12−ij = \frac{m + n + 1}{2} - i

  3. 现在我们有 len(left_part)=len(right_part)\text{len}(\text{left}\_\text{part})=\text{len}(\text{right}\_\text{part})。 而且我们只会遇到三种情况：

    • B[j−1]≤A[i]\text{B}[j-1] \leq \text{A}[i] 且 A[i−1]≤B[j]\text{A}[i-1] \leq \text{B}[j]：
      这意味着我们找到了目标对象 ii，所以可以停止搜索。

    • B[j−1]>A[i]\text{B}[j-1] > \text{A}[i]：
      这意味着 A[i]\text{A}[i] 太小，我们必须调整 ii 以使 B[j−1]≤A[i]\text{B}[j-1] \leq \text{A}[i]。
      我们可以增大 ii 吗？
            是的，因为当 ii 被增大的时候，jj 就会被减小。
            因此 B[j−1]\text{B}[j-1] 会减小，而 A[i]\text{A}[i] 会增大，那么 B[j−1]≤A[i]\text{B}[j-1] \leq \text{A}[i] 就可能被满足。
      我们可以减小 ii 吗？
            不行，因为当 ii 被减小的时候，jj 就会被增大。
            因此 B[j−1]\text{B}[j-1] 会增大，而 A[i]\text{A}[i] 会减小，那么 B[j−1]≤A[i]\text{B}[j-1] \leq \text{A}[i] 就可能不满足。
      所以我们必须增大 ii。也就是说，我们必须将搜索范围调整为 [i+1,imax][i+1, \text{imax}]。 因此，设 imin=i+1\text{imin} = i+1，并转到步骤 2。

    • A[i−1]>B[j]\text{A}[i-1] > \text{B}[j]： 这意味着 A[i−1]\text{A}[i-1] 太大，我们必须减小 ii 以使 A[i−1]≤B[j]\text{A}[i-1]\leq \text{B}[j]。 也就是说，我们必须将搜索范围调整为 [imin,i−1][\text{imin}, i-1]。
      因此，设 imax=i−1\text{imax} = i-1，并转到步骤 2。

当找到目标对象 ii 时，中位数为：

max⁡(A[i−1],B[j−1]), \max(\text{A}[i-1], \text{B}[j-1]), \ 当 m+nm + n 为奇数时

max⁡(A[i−1],B[j−1])+min⁡(A[i],B[j])2, \frac{\max(\text{A}[i-1], \text{B}[j-1]) + \min(\text{A}[i], \text{B}[j])}{2}, \ 当 m+nm + n 为偶数时

现在，让我们来考虑这些临界值 i=0,i=m,j=0,j=ni=0,i=m,j=0,j=n，此时 A[i−1],B[j−1],A[i],B[j]\text{A}[i-1],\text{B}[j-1],\text{A}[i],\text{B}[j] 可能不存在。 其实这种情况比你想象的要容易得多。

我们需要做的是确保 max(left_part)≤min(right_part)\text{max}(\text{left}\_\text{part}) \leq \text{min}(\text{right}\_\text{part})。 因此，如果 ii 和 jj 不是临界值（这意味着 A[i−1],B[j−1],A[i],B[j]\text{A}[i-1], \text{B}[j-1],\text{A}[i],\text{B}[j] 全部存在）, 那么我们必须同时检查 B[j−1]≤A[i]\text{B}[j-1] \leq \text{A}[i] 以及 A[i−1]≤B[j]\text{A}[i-1] \leq \text{B}[j] 是否成立。 但是如果 A[i−1],B[j−1],A[i],B[j]\text{A}[i-1],\text{B}[j-1],\text{A}[i],\text{B}[j] 中部分不存在，那么我们只需要检查这两个条件中的一个（或不需要检查）。 举个例子，如果 i=0i = 0，那么 A[i−1]\text{A}[i-1] 不存在，我们就不需要检查 A[i−1]≤B[j]\text{A}[i-1] \leq \text{B}[j] 是否成立。 所以，我们需要做的是：

在 [0，m][0，m] 中搜索并找到目标对象 ii，以使：

(j=0(j = 0 or i=mi = m or B[j−1]≤A[i])\text{B}[j-1] \leq \text{A}[i]) 或是 (i=0(i = 0 or j=nj = n or A[i−1]≤B[j]),\text{A}[i-1] \leq \text{B}[j]), 其中 j=m+n+12−ij = \frac{m + n + 1}{2} - i

在循环搜索中，我们只会遇到三种情况：

  1. (j=0(j = 0 or i=mi = m or B[j−1]≤A[i])\text{B}[j-1] \leq \text{A}[i]) 或是
    (i=0(i = 0 or j=nj = n or A[i−1]≤B[j])\text{A}[i-1] \leq \text{B}[j])
    这意味着 ii 是完美的，我们可以停止搜索。
  2. j>0j > 0 and i<mi < m and B[j−1]>A[i]\text{B}[j - 1] > \text{A}[i]
    这意味着 ii 太小，我们必须增大它。
  3. i>0i > 0 and j<nj < n and A[i−1]>B[j]\text{A}[i - 1] > \text{B}[j]
    这意味着 ii 太大，我们必须减小它。

感谢 @Quentin.chen 指出： i<m  ⟹  j>0i < m \implies j > 0 以及 i>0  ⟹  j<ni > 0 \implies j < n 始终成立，这是因为：

m≤n, i<m  ⟹  j=m+n+12−i>m+n+12−m≥2m+12−m≥0m \leq n,\ i < m \implies j = \frac{m+n+1}{2} - i > \frac{m+n+1}{2} - m \geq \frac{2m+1}{2} - m \geq 0

m≤n, i>0  ⟹  j=m+n+12−i<m+n+12≤2n+12≤nm \leq n,\ i > 0 \implies j = \frac{m+n+1}{2} - i < \frac{m+n+1}{2} \leq \frac{2n+1}{2} \leq n

所以，在情况 2 和 3中，我们不需要检查 j>0j > 0 或是 j<nj < n 是否成立。

复杂度分析

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

  • 空间复杂度：O(1)O(1)， 我们只需要恒定的内存来存储 99 个局部变量， 所以空间复杂度为 O(1)O(1)。