[Leetcode] 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)).

Solution:

public class Solution {
    public double findMedianSortedArrays(int A[], int B[]) {
        int m=A.length;
        int n=B.length;
        int total=m+n;
        if(total%2!=0){
            return findKthNumber(A,m,B,n,total/2+1);
        }else{
            return (findKthNumber(A,m,B,n,total/2)+findKthNumber(A,m,B,n,total/2+1))/2;
        }
    }

    private double findKthNumber(int[] a, int m, int[] b, int n, int k) {
        // TODO Auto-generated method stub
        if(m>n)
            return findKthNumber(b, n, a, m, k);
        if(m==0)
            return b[k-1];
        if(k==1)
            return Math.min(a[0], b[0]);
        int pa=Math.min(k/2, m);
        int pb=k-pa;
        if(a[pa-1]<b[pb-1]){
            int[] c=Arrays.copyOfRange(a, pa, m);
            return findKthNumber(c, m-pa, b,n, k-pa);
        }else if(a[pa-1]>b[pb-1]){
            int[] d=Arrays.copyOfRange(b, pb, n);
            return findKthNumber(a, m, d, n-pb, k-pb);
        }else{
            return a[pa-1];
        }
    }
}

此题甚难啊觉得。。。

可以参考一下大神的图，再自己看看代码改改图就可以理解啦：

http://www.narutoacm.com/archives/median-of-two-sorted-arrays/