本文共 2453 字，大约阅读时间需要 8 分钟。

class Solution {//more detail refer to: http://fisherlei.blogspot.com/2012/12/leetcode-median-of-two-sorted-arrays.html//using the method of getting the kth number in the two sorted array to solve the median problem//divide-and-conquer//very clean and concisepublic:	double findMedianSortedArrays(int A[], int m, int B[], int n) {  		if((n+m)%2 ==0)  		{  			return (GetMedian(A,m,B,n, (m+n)/2) + GetMedian(A,m,B,n, (m+n)/2+1))/2.0;  		}  		else  			return GetMedian(A,m,B,n, (m+n)/2+1);        	}  	int GetMedian(int a[], int n, int b[], int m, int k)//get the kth number in the two sorted array  	{  		//assert(a && b);   		if (n <= 0) return b[k-1];  		if (m <= 0) return a[k-1];  		if (k <= 1) return min(a[0], b[0]);   		//a: section1 section2		//b: section3 section4		if (b[m/2] >= a[n/2])  		{  			if ((n/2 + 1 + m/2) >= k)  				return GetMedian(a, n, b, m/2, k);//abort section 4  			else  				return GetMedian(a + n/2 + 1, n - (n/2 + 1), b, m, k - (n/2 + 1)); //abort section 1 		}  		else  		{  			if ((m/2 + 1 + n/2) >= k)  				return GetMedian( a, n/2,b, m, k);//abort section 2			else  				return GetMedian( a, n, b + m/2 + 1, m - (m/2 + 1),k - (m/2 + 1));//abort section 3		}  	}  };

second time

class Solution {public:    int GetKthNumber(int A[], int m, int B[], int n, int k)    {        //terminate case        if(m <= 0) return B[k];        if(n <= 0) return A[k];        if(k <= 0) return min(A[0], B[0]);        //recursion        //A:s1,median,s2        //B:s3,median,s4        if(A[m/2] > B[n/2])//s2>s3        {            if(m/2+n/2+1 >= k+1)            {                //A:s1                //B:s3,median,s4                GetKthNumber(A, m/2, B, n, k);            }            else            {                //A:s1,median,s2                //B:s4                GetKthNumber(A, m, B+(n/2+1), n-(n/2+1), k-(n/2+1));            }        }        else//A[m/2] < B[n/2]        {            if(m/2+n/2+1 >= k+1)                GetKthNumber(A, m, B, n/2, k);            else                GetKthNumber(A+(m/2+1), m-(m/2+1), B, n, k-(m/2+1));        }    }    double findMedianSortedArrays(int A[], int m, int B[], int n) {        // Start typing your C/C++ solution below        // DO NOT write int main() function        if((m+n)%2 == 0)//even            return (double)(GetKthNumber(A, m, B, n, (m+n)/2-1)+GetKthNumber(A, m, B, n, (m+n)/2))/2.0;        else             return (double)GetKthNumber(A, m, B, n, (m+n)/2);    }};

转载地址：http://llxti.baihongyu.com/