Leetcode: Median of Two Sorted Arrays.

Median of Two Sorted Arrays.cpp

class Solution {
public:
    double findMedianSortedArrays(int A[], int m, int B[], int n) {
        int N = m+n;
        if (N%2) return findKth(A, m, B, n, N/2+1);
        else return (double(findKth(A, m, B, n, N/2)) + findKth(A, m, B, n, N/2+1))/2;
    }
    int findKth(int A[], int m, int B[], int n, int k) {
        if (m > n) return findKth(B, n, A, m, k);
        if (m==0) return B[k-1];
        if (k==1) return min(A[0], B[0]);
        
        int t = min(k/2, m);
        int t2 = k-t;
        if (A[t-1] < B[t2-1])
            return findKth(A+t, m-t, B, n, k-t);
        else return findKth(A, m, B+t2, n-t2, k-t2);
    }
};

这道题应该是在大众点评二面之前看过解法的。
在leetcode discuss区，这个解法没有被顶到第一名，真的很奇怪。

他的思路非常好，解决的不止是找到median，而是找到Kth biggest number。
利用findKth函数自身，把【从A，B中找第K大的数】，转换成【在A，B的子数组中找第K/2大的数】

Boundary Cases：

1. 一个数组为空（大小为0）
2. 当两个数组的大小之和（记为N）为偶数的时候，通常我们只要找第N/2+1大的元素就可以了，这道题要求我们找出第N/2大的元素和第N/2+1大的元素，求平均；所以输入为int型的数组，返回的中位数类型是double。