Median of Two Sorted Array

出处

Solution

对于含有n个数的数组,若n为奇数,则中位数array[n/2+1],若n为偶数,则中位数为 (array[n/2] + array[n/2+1]) / 2。所以我们当前的目标是设计一种算法能够返回第k大的元素。对于查找第k大的数,最先想到的应该是快速选择算法,但是该算法并没有利用数组已经有序的特性,故时间复杂度O(m+n)。与二分查找相似,快速选择算法的核心在于快速缩小搜索范围。

对于本例,我们应该如何缩小搜索范围呢?假设数组分别记为A,B。当前需要搜索第k大的数,于是我们可以考虑从数组A中取出前m个元素,从数组B中取出k-m个元素。由于数组A,B分别排序,则A[m]大于从数组A中取出的其他所有元素,B[k-m] 大于数组B中取出的其他所有元素。此时,尽管取出元素之间的相对大小关系不确定,但A[m]与B[k-m]的较大者一定是这k个元素中最大的。那么,较小的那个元素一定不是第k大的,它至多是第k-1大的:因为它小于其他未被取出的所有元素,并且小于取出的k个元素中最大的那个。为叙述方便,假设A[m]是较小的那个元素。那么,我们可以进一步说,A[1], A[2]…A[m-1]也一定不是第k大的元素,因为它们小于A[m],而A[m]至多是第k-1大的。因此,我们可以把较小元素所在数组中选出的所有元素统统排除,并且相应地减少k值。这样,我们就完成了一次范围缩小。特别地,我们可以选取m=k/2。


将原问题转变成一个寻找第k小数的问题(假设两个原序列升序排列),这样中位数实际上是第(m+n)/2小的数。所以只要解决了第k小数的问题,原问题也得以解决。

首先假设数组A和B的元素个数都大于k/2,我们比较A[k/2-1]和B[k/2-1]两个元素,这两个元素分别表示A的第k/2小的元素和B的第k/2小的元素。这两个元素比较共有三种情况:>、<和=。如果A[k/2-1]<B[k/2-1],这表示A[0]到A[k/2-1]的元素都在A和B合并之后的前k小的元素中。换句话说,A[k/2-1]不可能大于两数组合并之后的第k小值,所以我们可以将其抛弃。

证明也很简单,可以采用反证法。假设A[k/2-1]大于合并之后的第k小值,我们不妨假定其为第(k+1)小值。由于A[k/2-1]小于B[k/2-1],所以B[k/2-1]至少是第(k+2)小值。但实际上,在A中至多存在k/2-1个元素小于A[k/2-1],B中也至多存在k/2-1个元素小于A[k/2-1],所以小于A[k/2-1]的元素个数至多有k/2+ k/2-2,小于k,这与A[k/2-1]是第(k+1)的数矛盾。

当A[k/2-1]>B[k/2-1]时存在类似的结论。

当A[k/2-1]=B[k/2-1]时,我们已经找到了第k小的数,也即这个相等的元素,我们将其记为m。由于在A和B中分别有k/2-1个元素小于m,所以m即是第k小的数。(这里可能有人会有疑问,如果k为奇数,则m不是中位数。这里是进行了理想化考虑,在实际代码中略有不同,是先求k/2,然后利用k-k/2获得另一个数。)

通过上面的分析,我们即可以采用递归的方式实现寻找第k小的数。此外我们还需要考虑几个边界条件:

  • 如果A或者B为空,则直接返回B[k-1]或者A[k-1];
  • 如果k为1,我们只需要返回A[0]和B[0]中的较小值;
  • 如果A[k/2-1]=B[k/2-1],返回其中一个;

Complexity

每次缩小范围之后k值基本上折半,故时间复杂度O(logn)。

Code

double helper(int A[], int m, int B[], int n, int k){
    // find the kth largest element
    if(m > n)
        return helper(B, n, A, m, k);//make sure that the second one is the bigger array;
    if(m == 0)
        return B[k - 1];
    if(k == 1){
        return min(A[0], B[0]);
    }
    int pa = min(k / 2, m); // assign k / 2 to each of the array and cut the smaller one
    int pb = k - pa;
    if (A[pa-1] <= B[pb-1])
        return helper(A + pa, m - pa, B, n, k - pa);
    return helper(A, m, B + pb, n - pb, k - pb);
}

double findMedianSortedArrays(int A[], int m, int B[], int n) {
    int total = m + n;
    if(total % 2 == 0){
        return (helper(A, m, B, n, total / 2) + helper(A, m, B, n, total / 2 + 1)) / 2;
    }
    return helper(A, m, B, n, total / 2 + 1);
}