中位数例题解法摘录

LeetCode题目：给定两个顺序存储的升序整数序列A和B，A的长度为M，B的长度为N。计算由A和B组合而成的新序列的中位数。

看到中位数，你应能联想到计算无序整数序列中第K小数字的算法。那个算法不断地划分序列以使其部分有序，在每轮循环中确定中位数所在的大概位置，舍弃所有关系已知的数据。对数级复杂度来源于朴素的二分思想。你所要做的就是在每一轮循环中分析中位数的大概位置并尽可能多地舍弃数据。

你可能会想到这么做：对于序列A_0,A_1...A_{k/2-1}...A_{M-1}和B_0,B_1...B_{k/2-1}...B_{M-1}来说，如果A_{k/2-1}小于B_{k/2-1}，那么就会有关系：A_0ㄑA_1ㄑ...ㄑA_{k/2-1}ㄑB_{k/2-1}。如果B_0,B_1...B_{k/2-2}都比A_{k/2-1}小，那么比A_{k/2-1}小的数字最多也只有K-2个，序列A的首部共k/2个元素可以全部舍弃。此时中位数在A_{k/2}...A{M-1}和序列B中。

下面的子过程说明了如何在升序序列A和B中寻找第K小的整数。

int kth(int* a, int* b, int asize, int bsize, int k) {
    int p = 0, q = 0, s, t;
LP:
    //此序列越界，去另一个序列种找第K小的整数
    if (p == asize) return b[q + k - 1];
    if (q == bsize) return a[p + k - 1];
    //K变成1，即计算最小值
    if (k == 1) return a[p] < b[q] ? a[p] : b[q];
    s = p + k / 2;
    if (asize < s) s = asize;
    t = q + k / 2;
    if (bsize < t) t = bsize;
    //执行完下一行 s=min{p+k/2-1, asize-1},t同理
    if (a[--s] <= b[--t]) {
        k -= s - p + 1;
        p = s + 1;
    } else {
        k -= t - q + 1;
        q = t + 1;
    }
    goto LP;
}

何为中位数？有序整数序列X的中位数H将X分成等长的两段，右侧数字均大于H而左边小于H。既然这样，如果能够找到这样一组数(C,D)将A和B分别划分为A_0,A_1...A_C...A_{M-1}和B_0,B_1...B_D...B_{N-1}，使A的左部与B的左部合并成为前半段L（不包含A_C、B_D），A的右部与B的右部合并成为后半段R（包含A_C、B_D）。如果L与R等长或者L比R长度大1，而且前半段的最大值小于后半段的最小值，那么中位数便可以直接解出。

为此，Partition(C,D)需要同时满足：0<=C<=M、0<=D<=N、C+D=[(M-C)+(N-D)]或C+D=[(M-C)+(N-D)]+1、Max(L)<=Min(R)这四个条件（使用无穷大值处理位于序列边界的划分）。

第三个条件等价于：C=??(M+N+1)/2??-D，第四个条件等价于：A_{C-1}<=B_D且B{D-1}<=A_C，又因为C=??(M+N+1)/2??-D而A和B都是升序序列，所以若C递增则A_C递增、B_D递减，故又等价于C=Max{x|A_{x-1}<=B_y，y=??(M+N+1)/2??-x}。

你要做的就是在序列A上使用二分法寻找满足条件的最大C值。若总是选择序列长度最小的序列当作A，那么时间复杂度就是lg(A.size)。