学步园

class Solution {
public:
    int findKth(int k,int *A,int m,int *B, int n){//index=k
        int r1=m-1,r2=n-1;
        //assert(r1+r2=2>=k+1);
        while(true){
            if(r1<0) return B[k];
            else if(r2<0) return A[k];
            else if(r1+r2+2==k+1) return max(A[r1],B[r2]);
            
            int m1=(k+2)*(1+r1)/(r1+r2+2)-1,m2=k-m1;
           
            if(m1<0) m1=0,m2=k-m1;
            if(m2<0) m2=0,m1=k-m2;
 
            assert(m1<=r1&&m1>=0);
            assert(m2<=r2&&m2>=0);
            
            if(A[m1]>=B[m2]) r1=m1-1;////////@@@@@error:  if(A[m1]>=A[m2]) : the condition has written wrong. array B fault as A.
            else r2=m2-1;
        }
    }
    double findMedianSortedArrays(int A[], int m, int B[], int n) {
        int i=(m+n)/2-1,j=i+1;
        if((m+n)%2==0){ 
            return ((double)findKth(i,A,m,B,n)+findKth(j,A,m,B,n))/2;
        }else{
            return (double)findKth(j,A,m,B,n);
        }
    }
};

另一种写法

class Solution {
public:
    double findMedianSortedArrays(int A[], int m, int B[], int n) {
        int len = (m+n);
        if( len%2 == 1 )
           return findK(A, m, B, n, (m+n+1)/2);
        else {
           double x=findK(A, m, B, n, (m+n)/2) ;
           double y=findK(A, m, B, n, (m+n)/2+1);
           double z=x+y;

           return z/2;
           //return z/2;
        }
    }
     int findK(int A[], int m, int B[], int n, int k){
       // assert(m+n >= k && k > 0);
        int r1 = m-1, r2 = n-1;
        while(r1+r2+2>=k+1 && r1>=0 && r2>=0){
            //int m1 = (r1+1)*(k-1)/(r1+r2+2), m2=k-1-m1; //@error： 
            //int m1 = (r1+1)*k/(r1+r2+2)-1, m2=k-1-m1;//@error
            int m1 = (k+1)*(r1+1)/(r1+r2+2)-1, m2=k-1-m1; //应该先算长度，再-1变成坐标
            if(m1<0) m1=0, m2=k-1;
            //assert(m1<=r1 && m2<=r2);
            if(A[m1]>B[m2]) r1=m1-1;
            else r2=m2-1;
        }
        if(r1<0 || r2<0) return r1<0?B[k-1]:A[k-1];// k-1
        return A[r1]>B[r2]?A[r1]:B[r2];
    }

};