AC Code
public class Solution {public double findMedianSortedArrays(int A[], int B[]) {int m = A.length;int n = B.length;if((m + n) % 2 == 0){return (findKth(A, B, 0, m – 1, 0, n – 1, (m + n) / 2) + findKth(A, B, 0, m – 1, 0, n – 1, (m + n) / 2 + 1)) / 2.0;} else {return findKth(A, B, 0, m – 1, 0, n – 1, (m + n) / 2 + 1);}}public int findKth(int A[], int B[], int Al, int Ar, int Bl, int Br, int k){//find the Kth element in the the merged array from A and Bint m = Ar – Al + 1;int n = Br – Bl + 1;if(m > n){//let the length of A is always shorter than the length of Breturn findKth(B, A, Bl, Br, Al, Ar, k);}if(m == 0){return B[Bl + k – 1];}if(k == 1){return Math.min(A[Al], B[Bl]);}int posA = Math.min(k / 2, m);int posB = k – posA;if(A[Al + posA – 1] < B[Bl + posB – 1]) {//In this case, find the (k-posA)th element in the right of A and left of Breturn findKth(A, B, Al + posA, Ar, Bl, Bl + posB -1, k – posA);} else if(A[Al + posA – 1] > B[Bl + posB – 1]){//In this case, find the (k – posB)th element in the right of B and left of Areturn findKth(A, B, Al, Al + posA – 1, Bl + posB, Br, k – posB);} else {return A[Al + posA – 1];//In this case, both A[Al + posA – 1] and B[Bl + posB – 1] are the kth element we want to find}}}参考了
，有时间，我们可以去爬山，
