//from sui's google round1 public class SearchKthNumber { private int[] aArray; private int[] bArray; public SearchKthNumber(int[] aArray, int[] bArray){ this.aArray = aArray; this.bArray = bArray; if(this.aArray == null || this.bArray == null){ throw new RuntimeException("Array can not be null"); } } public int doSearch(int aLeft, int aRight, int bLeft,int bRight, int k ){ int aMiddle = (aLeft + aRight)/2; int bMiddle = (bLeft + bRight)/2; if(aLeft>aRight){ return bArray[bLeft+k-1]; } if(bLeft>bRight){ return aArray[aLeft+k-1]; } if(aArray[aMiddle] > bArray[bMiddle]){ if(k<=(aMiddle - aLeft)+(bMiddle - bLeft)+1){ return doSearch(aLeft,aMiddle-1,bLeft,bRight,k); } else{ return doSearch(aLeft,aRight,bMiddle+1,bRight,k-(bMiddle-bLeft)-1); //move k as well as subtract distance from a } } else{ if(k<=(aMiddle - aLeft)+(bMiddle - bLeft)+1){ return doSearch(aLeft,aRight,bLeft,bMiddle-1,k); } else{ return doSearch(aMiddle+1,aRight,bLeft,bRight,k-(aMiddle-aLeft)-1); } } } public static void main(String[] args){ int[] aArray=new int[]{1,3,5,6,8,9,11,18,20}; int[] bArray=new int[]{2,4,7,16,22,29,39,40,55,100}; SearchKthNumber sn=new SearchKthNumber(aArray,bArray); int k=2; int result=sn.doSearch(0,aArray.length-1,0,bArray.length-1,k); System.out.println("The "+k+"th"+" Number : "+result); } }
public class Solution { public double findMedianSortedArrays(int A[], int B[]) { int m = A.length; int n = B.length; if( (m + n) % 2 != 0 ) // odd number of total elements return (double)findKth(A, B, (m + n) / 2, 0, m-1, 0, n-1); else { // even return ( findKth(A, B, (m + n) / 2, 0, m-1, 0, n-1) + findKth(A, B, (m + n) / 2 - 1, 0, m-1, 0, n-1) ) * 0.5; } } public static int findKth(int A[], int B[], int k, int ista_A, int iend_A, int ista_B, int iend_B) { int nA = iend_A - ista_A + 1; int nB = iend_B - ista_B + 1; // Special cases if( nA == 0 ) return B[ista_B + k]; if( nB == 0 ) return A[ista_A + k]; if( k == 0) return A[ista_A] < B[ista_B] ? A[ista_A] : B[ista_B]; // Reduce search ranges in A and B int imid_A = nA * k / (nA + nB); int imid_B = k - imid_A - 1; // Add offset so that imid_A and imid_B index directly into A and B, // respectively imid_A += ista_A; imid_B += ista_B; if( A[imid_A] > B[imid_B] ) { k -= imid_B - ista_B + 1; iend_A = imid_A; ista_B = imid_B + 1; } else { k -= imid_A - ista_A + 1; iend_B = imid_B; ista_A = imid_A + 1; } return findKth(A, B, k, ista_A, iend_A, ista_B, iend_B); } }