[leetcode]Median of Two Sorted Arrays

问题就是找两个排序数组里面第k大的数

 

我们在A，B前k/2里面，比较A[k/2] , B[k/2]

哪个小说明第k个肯定不在里面，可以抛弃，然后继续递归处理

 

class Solution {
public:

    /**
    * choice k/2 from a, and k/2 from b
    * compare the last
    * if b[k/2] > a[k/2], drop a[k/2], kth must not in a[k/2]
    * otherwise the same
    */
    double findMedianSortedArrays(int A[], int m, int B[], int n) {
        int total = m + n;
        if(total % 2 == 0) {
            return (double)(kth(A,m,B,n,total/2) + kth(A,m,B,n,total/2+1))/2;
        }else {
            return (double)kth(A,m,B,n,total/2+1);
        }
    }
private:
    int kth(int A[] , int m , int B[] , int n , int k) {
        if(n < m) return kth(B , n , A , m ,k);
        if(m == 0) return B[k-1]; 
        if(k == 1) return min(A[0] , B[0]);
        
        // am bn
        int pa = min(k/2 , m);
        int pb = k - pa;
        
        if(A[pa-1] < B[pb-1])
            return kth(A+pa , m - pa , B , n , k-pa);
        else if(A[pa-1] > B[pb-1])
            return kth(A , m , B+pb , n-pb , k-pb);
        else 
            return A[pa-1];
    }
};