康瑞部落

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)).

解题思路：

最基本的办法是合并排序法，先将两个数组合并成一个数组，然后计算中位数的值（他的一个改进版就是计数）。但时间复杂度为O(m+n)，不满足题目的要求。我完全没有思路，在网上查找的解题思路如下：

将原题看成是找第k小的数，递归查找结果。几个边界条件为：

• 如果A或者B为空，则直接返回B[k-1]或者A[k-1]；

• 如果k为1，我们只需要返回A[0]和B[0]中的较小值；

• 如果A[k/2-1]=B[k/2-1]，返回其中一个；

实现代码：

class Solution {
public:
    double findMedianSortedArrays(int A[], int m, int B[], int n) {
        int total = m + n;
        if(total & 1 ) {    //奇数
            return findKth(A, m, B, n, ((m + n) >> 1) + 1);
        }else{  //偶数
            return (findKth(A, m, B, n, (m + n) >> 1) + findKth(A, m, B, n, ((m + n) >> 1) + 1)) / 2;
        }
    }
    
    double 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 pa = min(k >> 1, m), pb = k - pa;
        //排除小的那部分
        if(A[pa-1] < B[pb-1]){
            return findKth(A + pa, m - pa, B, n, k - pa);
        }else if(A[pa - 1] > B[pb - 1]){
            return findKth(A, m, B + pb, n - pb, k - pb);
        }else{
            return A[pa-1];
        }
    }
private:
    int min(int a, int b){
        return a>b?b:a;
    }
};

有几个地方可以值得借鉴：状态转化思想，因为findKth不知道两个数组哪个更长些，为了免除不必要的判断，直接转化为其中一种状态，我们在编码的时候只需要考虑一种状态即可。

二次刷题（2015-08-18）

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size();
        int n = nums2.size();
        int total = m + n;
        if(total&1){
            return getKth(nums1, 0, m-1, nums2, 0, n-1, (total>>1) + 1);
        }else{
            return (getKth(nums1, 0, m-1, nums2, 0, n-1, total>>1) + getKth(nums1, 0, m-1, nums2, 0, n-1, (total>>1) + 1))/2;
        }
    }
    
    double getKth(vector<int>& nums1, int start1, int end1, vector<int>& nums2, int start2, int end2, int k){
        int m = end1 - start1 + 1;
        int n = end2 - start2 + 1;
        if(m > n){
            return getKth(nums2, start2, end2, nums1, start1, end1, k);
        }
        if(m<=0){
            return nums2[start2 + k - 1];
        }
        if(k==1){
            return min(nums1[start1], nums2[start2]);
        }
        int pa = min(k>>1, m), pb = k - pa;
        if(nums1[start1 + pa - 1] < nums2[start2 + pb - 1]){
            return getKth(nums1, start1 + pa, end1, nums2, start2, end2, k - pa);
        }else if(nums1[start1 + pa - 1] > nums2[start2 + pb - 1]){
            return getKth(nums1, start1, end1, nums2, start2 + pb, end2, k - pb);
        }else{
            return nums1[start1 + pa - 1];
        }
    }
};

参考网址：http://blog.csdn.net/yutianzuijin/article/details/11499917