考研笔记

板子：两个等长升序序列的中位数

长度为 的升序序列，中位数是第 个数。两个长度都为 的序列合起来有 个数，中位数就是第 小的数。

保底解：按合并顺序数到第 n 个

int midMerge(int A[], int B[], int n) {
    int i = 0, j = 0, x = 0;
    for (int k = 0; k < n; k++)            // 第 k 次取之前只取了 k 个，i、j 都不超过 n-1，不会越界
        x = A[i] <= B[j] ? A[i++] : B[j++];
    return x;
}

复杂度：时间 ，空间 。思路就是 有序表合并，只数不存。

满分解：每轮两边各砍一半

设 A、B 当前区间的中位数分别是 、：

  • ：它就是答案。
  • ：答案在 A 的后半段、B 的前半段。舍掉 A 较小的一半和 B 较大的一半，两边舍掉的个数必须相等。
  • ：反过来。
  • 两个区间都只剩一个元素时，较小的那个就是答案。
int midSearch(int A[], int B[], int n) {
    int s1 = 0, d1 = n - 1, s2 = 0, d2 = n - 1;   // 当前区间 A[s1..d1]、B[s2..d2]，长度始终相等
    while (s1 != d1 || s2 != d2) {                // 两个区间都只剩一个元素时停
        int m1 = (s1 + d1) / 2, m2 = (s2 + d2) / 2;   // 两边的中点；两区间等长，奇偶性相同
        if (A[m1] == B[m2]) return A[m1];
        if (A[m1] < B[m2]) {                      // 舍掉 A 的前半、B 的后半
            s1 = (d1 - s1 + 1) % 2 ? m1 : m1 + 1; // 奇数个时保留中点；偶数个时中点也舍掉
            d2 = m2;
        } else {                                  // 舍掉 A 的后半、B 的前半
            s2 = (d2 - s2 + 1) % 2 ? m2 : m2 + 1;
            d1 = m1;
        }
    }
    return A[s1] < B[s2] ? A[s1] : B[s2];
}

复杂度：时间 ，空间 。

例：A = (11,13,15,17,19)，B = (2,4,6,8,20)，中位数是 11。

易错点

  • 中位数的定义是第 个数， 个数的中位数就是第 小，不是中间两个数的平均。
  • 满分解里偶数个元素时，中位数较小的那一边要连中点一起舍掉，否则两边剩下的长度不相等。
  • 满分解想不清楚就写保底解，保底解是正确的，只是不够优。

链接

反向链接