线性表-Median of Two Sorted Arrays

描述：

There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log(m + n)).

思路：

这道题更通用的形式是，给定两个已经排好序的数组，找到两者所有元素中的第k大的元素。
O（m+n）的解法比较直观，直接merge两个数组，然后求第k大的元素。
如果仅仅找到第k大的元素，我们并不需要进行排序，可以用一个计数器，记录当前已经找到第m大的元素。我们同时使用pa和pb两个指针，分别指向A和B数组中的第一个元素，如果当前数组A元素小，那么pa++，同时m++，如果数组B当前元素小，那么pb++，同时m++。最终当m等k的时候，就得到了我们的答案，当k很接近m+n的时候，这个方法还是O（m+n）。
如果每次我们都能够删除一个一定在第k大元素之前的元素，那么我们需要进行k次，但如果我们每次都删除一半呢？由于A和B都是有序的，我们可以利用二分的思想来解决。假设A和B元素的个数都大于k/2，我们将A的k/2个元素（即A[k/2-1]）和B的第k/2个元素（即B[k/2-1]）进行比较，有以下三种情况：
• A[k/2-1] == B[k/2-1]
• A[k/2-1] > B[k/2-1]
• A[k/2-1] < B[k/2-1]
如果 A[k/2-1] < B[k/2-1]，意味着A[0]到A[k/2-1]中不可能有第k大的元素，因此，可以删除A数组中的着k/2个元素，同理，A[k/2-1] > B[k/2-1]时，可以删除B数组的k/2个元素。当A[k/2-1] == B[k/2-1]时，说明找到了第k大的元素，直接返回A[k/2-1] 或 B[k/2-1]。
因此我们写了一个递归函数，那么函数什么时候应该终止呢？
当A或B是空时，直接返回A[k/2-1] 或 B[k/2-1]
当k=1时，返回的是min（A[0],B[0]）；
当A[k/2-1] == B[k/2-1]时，返回A[k/2-1] 或 B[k/2-1]

class Solution {
public:
    double findMedianSortedArrays(vector<int>& A, vector<int>& B) {
        const int m = A.size();
        const int n = B.size();
        int total = m + n;
        if (total & 0x1)
        return find_kth(A.begin(), m, B.begin(), n, total / 2 + 1);
        else
        return (find_kth(A.begin(), m, B.begin(), n, total / 2)
        + find_kth(A.begin(), m, B.begin(), n, total / 2 + 1)) / 2.0;
}
private:
        static int find_kth(std::vector<int>::const_iterator A, int m,
        std::vector<int>::const_iterator B, int n, int k) {
        //always assume that m is equal or smaller than n
        if (m > n) return find_kth(B, n, A, m, k);
        if (m == 0) return *(B + k - 1);
        if (k == 1) return min(*A, *B);
        //divide k into two parts
        int ia = min(k / 2, m), ib = k - ia;
        if (*(A + ia - 1) < *(B + ib - 1))
        return find_kth(A + ia, m - ia, B, n, k - ia);
        else if (*(A + ia - 1) > *(B + ib - 1))
        return find_kth(A, m, B + ib, n - ib, k - ib);
        else
        return A[ia - 1];
    }    
};