解决方案


方法:递归法

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

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

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

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

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

由于 中有 个元素, 所以我们有 种划分的方法()。

我们知道:

.

注意:当 时, 为空集, 而当 时, 为空集。

采用同样的方式,我们在任一位置 划分成两个部分:

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

放入一个集合,并将 放入另一个集合。 再把这两个新的集合分别命名为

          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. (或:) 如果 ,只需要使

  2. 以及

ps.1 为了简化分析,我假设 总是存在,哪怕出现 ,或是 这样的临界条件。 我将在最后讨论如何处理这些临界值。

ps.2 为什么 ?由于,我必须确保 不是负数。如果 ,那么 将可能是负数,而这会造成错误的答案。

所以,我们需要做的是:

中搜索并找到目标对象 ,以使:

其中

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

  1. , 然后开始在 中进行搜索。
  2. 现在我们有 。 而且我们只会遇到三种情况:


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


    • 这意味着 太小,我们必须调整 以使
      我们可以增大 吗?
            是的,因为当 被增大的时候, 就会被减小。
            因此 会减小,而 会增大,那么 就可能被满足。
      我们可以减小 吗?
            不行,因为当 被减小的时候, 就会被增大。
            因此 会增大,而 会减小,那么 就可能不满足。
      所以我们必须增大 。也就是说,我们必须将搜索范围调整为 。 因此,设 ,并转到步骤 2。

    • : 这意味着 太大,我们必须减小 以使 。 也就是说,我们必须将搜索范围调整为
      因此,设 ,并转到步骤 2。

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

为奇数时

为偶数时

现在,让我们来考虑这些临界值 ,此时 可能不存在。 其实这种情况比你想象的要容易得多。

我们需要做的是确保 。 因此,如果 不是临界值(这意味着 全部存在), 那么我们必须同时检查 以及 是否成立。 但是如果 中部分不存在,那么我们只需要检查这两个条件中的一个(或不需要检查)。 举个例子,如果 ,那么 不存在,我们就不需要检查 是否成立。 所以,我们需要做的是:

中搜索并找到目标对象 ,以使:

or or 或是 or or 其中

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

  1. or or 或是
    or or
    这意味着 是完美的,我们可以停止搜索。
  2. and and
    这意味着 太小,我们必须增大它。
  3. and and
    这意味着 太大,我们必须减小它。

感谢 @Quentin.chen 指出: 以及 始终成立,这是因为:

所以,在情况 2 和 3中,我们不需要检查 或是 是否成立。

复杂度分析

  • 时间复杂度:
    首先,查找的区间是 。 而该区间的长度在每次循环之后都会减少为原来的一半。 所以,我们只需要执行 次循环。由于我们在每次循环中进行常量次数的操作,所以时间复杂度为 。 由于 ,所以时间复杂度是

  • 空间复杂度:, 我们只需要恒定的内存来存储 个局部变量, 所以空间复杂度为