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) 解法：

1 public class Solution { 2     public double findMedianSortedArrays(int A[], int B[]) { 3         // Start typing your Java solution below 4         // DO NOT write main() function 5         double result = 0; 6         int lengthA = A.length; 7         int lengthB = B.length; 8          9         int[] combinedArray = new int[lengthA + lengthB];10         int i = 0;11         int j = 0;12         while(i < lengthA && j < lengthB){13             if(A[i] > B[j]){14                 combinedArray[i + j] = B[j];15                 j ++;16             }else{17                 combinedArray[i + j] = A[i];18                 i ++;19             }20         }21         if(i == lengthA){22             while(j < lengthB)23                 combinedArray[i + j] = B[j ++];24         }25         if(j == lengthB){26             while(i < lengthA)27                 combinedArray[i + j] = A[i ++];28         }29         30         if(((lengthA + lengthB) % 2) !=0){31             result = combinedArray[(lengthA + lengthB) / 2];32             //return combinedArray[(lengthA + lengthB) / 2];33         } else {34             result = (combinedArray[(lengthA + lengthB) / 2] + combinedArray[(lengthA + lengthB) / 2 - 1]) / 2.0;35             //return (combinedArray[(lengthA + lengthB) / 2] + combinedArray[(lengthA + lengthB) / 2 - 1]) / 2;36         }37         return result;38     }39 }

O(log (m+n)) 解法，肯定是二分：网上解法如下

1 public class Solution { 2     public double findMedianSortedArrays(int A[], int B[]) { 3         // Start typing your Java solution below 4         // DO NOT write main() function 5         int aLen = A.length; 6         int bLen = B.length; 7         if((aLen + bLen) % 2 ==0){ 8             return (getKthElement(A, 0, aLen - 1, B, 0, bLen - 1, (aLen + bLen) / 2) + getKthElement(A, 0, aLen - 1, B, 0, bLen - 1, (aLen + bLen) / 2 + 1)) / 2.0; 9         } else {10             return getKthElement(A, 0, aLen - 1, B, 0, bLen - 1, (aLen + bLen) / 2 + 1);11         }12     }13     14     public int getKthElement(int A[], int aBeg, int aEnd, int B[], int bBeg, int bEnd, int k){15         if(aBeg > aEnd){16             return B[bBeg + (k - 1)];17         }18         if(bBeg > bEnd){19             return A[aBeg + (k - 1)];20         }21         22         int aMid = (aBeg + aEnd) >> 1;23         int bMid = (bBeg + bEnd) >> 1;24         int len = aMid - aBeg + bMid - bBeg + 2;25         26         if(len > k){27             if(A[aMid] < B[bMid]){28                 return getKthElement(A, aBeg, aEnd, B, bBeg, bMid - 1, k);29             } else {30                 return getKthElement(A, aBeg, aMid - 1, B, bBeg, bEnd, k);31             }32         } else {33             if(A[aMid] < B[bMid]){34                 return getKthElement(A, aMid + 1, aEnd, B, bBeg, bEnd, k - (aMid - aBeg + 1));35             } else {36                 return getKthElement(A, aBeg, aEnd, B, bMid + 1, bEnd, k - (bMid - bBeg + 1));37             }38         }39     } 40 }

 第二遍：

 

1 public class Solution { 2     public double findMedianSortedArrays(int A[], int B[]) { 3         // Start typing your Java solution below 4         // DO NOT write main() function 5         int alen = A.length; 6         int blen = B.length; 7         if((alen + blen) % 2 == 1){ 8           return findKth(A, B, 0, alen - 1, 0, blen - 1, (alen + blen + 1) / 2); 9         }else{
   //当长度为偶数时，midian 是中间两个数之和除二。10           return (findKth(A, B, 0, alen - 1, 0, blen - 1, (alen + blen) / 2) + findKth(A, B, 0, alen - 1, 0, blen - 1, (alen + blen + 2) / 2)) / 2.0;11         }12     }13     14     public int findKth(int a[], int b[], int as, int ae, int bs, int be, int n){15         if(as > ae) return b[bs + n - 1];16         if(bs > be) return a[as + n - 1];17         int amid = (as + ae) / 2;18         int bmid = (bs + be) / 2;19         int len = amid - as + bmid - bs + 2;// 不能用全长 / 2， 因为前一半并不一定是整数。20         if(a[amid] > b[bmid]){21             if(n >= len){
   // 必须有等号， 因为a[amid] > b[bmid]， 所以b[bmid] 一定不是要取的值。22                 return findKth(a, b, as, ae, bmid + 1, be, n - (bmid - bs + 1));//每次只能去掉两个数组中某一个的一半。23             }24             else{25                 return findKth(a, b, as, amid - 1, bs, be, n);26             }27         }else{28             if(n >= len){29                 return findKth(a, b, amid + 1, ae, bs, be, n - (amid - as + 1));30             }31             else{32                 return findKth(a, b, as, ae, bs, bmid - 1, n);33             }34         }35     }36 }